Как эффективно подсчитать наличие набора чисел в наборе интервалов

Question

Входными параметрами являются список кортежей, представляющих интервалы, и список целых чисел. Цель состоит в том, чтобы написать функцию, которая подсчитывает количество интервалов, в которых присутствует каждое целое число, и возвращает этот результат в виде ассоциативного массива. Например:

Input intervals: [(1, 3), (5, 6), (6, 9)]
Input integers: [2, 4, 6, 8]
Output: {2: 1, 4: 0, 6: 2, 8: 1}

Другой пример:

Input intervals: [(3, 3), (22, 30), (17, 29), (7, 12), (12, 34), (18, 38), (30, 40), (5, 27), (19, 26), (27, 27), (1, 31), (17, 17), (22, 25), (6, 14), (5, 7), (9, 19), (24, 28), (19, 40), (9, 36), (2, 32)]
Input numbers: [16, 18, 39, 40, 27, 28, 4, 23, 15, 24, 2, 6, 32, 17, 21, 29, 31, 7, 20, 10]
Output: {2: 2, 4: 2, 6: 5, 7: 6, 10: 7, 15: 6, 16: 6, 17: 8, 18: 8, 20: 9, 21: 9, 23: 11, 24: 12, 27: 11, 28: 9, 29: 8, 31: 7, 32: 6, 39: 2, 40: 2}

Как бы я go написал о функции, которая делает это эффективно? У меня уже есть реализация O (nm) с n числом интервалов и m числом целых чисел, но я ищу что-то более эффективное.

Что у меня есть на данный момент:

def intervals_per_number(numbers, intervals):
    result_map = {i: 0 for i in numbers}
    for i in result_map.keys():
        for k in intervals:
            if k[0] <= i <= k[1]:
                result_map[i] += 1
    return result_map

Надеюсь, я объяснил это достаточно хорошо. Дайте мне знать, если что-то все еще неясно.

Заранее спасибо.

Answer 1

Поместите свои целые числа, начальные и конечные точки в один список пар. Сделайте для первого элемента каждой пары значение целого числа, начальной точки или конечной точки, а для второго элемента каждой пары - 0, -1 или 1, в зависимости от того, является ли это целое число, начальная точка или конечная точка.

Далее сортируйте список.

Теперь вы можете go просматривать список, сохраняя промежуточную сумму вторых элементов пар. Когда вы видите пару со вторым элементом 0, запишите промежуточную сумму (с отрицанием) для этого целого числа.

Это выполняется за O ((N + M) log (N + M)) в худшем случае ( и на практике я думаю, что это будет линейно, если запросы и интервалы будут в основном отсортированы, благодаря timsort).

Например:

Input intervals: [(1, 3), (5, 6), (6, 9)]
Input integers: [2, 4, 6, 8]

Unified list (sorted):
[(1,-1), (2,0), (3,1), (4,0), (5,-1), (6, -1), (6,0), (6,1), (8,0), (9,1)]

Running sum:
[-1    , -1,    0,     0,      -1,    -2,      0,      -1,    -1,   0]

Values for integers:
2: 1, 4: 0, 6: 2, 8, 1

Пример кода:

def query(qs, intervals):
    xs = [(q, 0) for q in qs] + [(x, -1) for x, _ in intervals] + [(x, 1) for _, x in intervals]
    S, r = 0, dict()
    for v, s in sorted(xs):
        if s == 0:
            r[v] = S
        S -= s
    return r

intervals = [(3, 3), (22, 30), (17, 29), (7, 12), (12, 34), (18, 38), (30, 40), (5, 27), (19, 26), (27, 27), (1, 31), (17, 17), (22, 25), (6, 14), (5, 7), (9, 19), (24, 28), (19, 40), (9, 36), (2, 32)]
queries = [16, 18, 39, 40, 27, 28, 4, 23, 15, 24, 2, 6, 32, 17, 21, 29, 31, 7, 20, 10]
print(query(queries, intervals))

Вывод:

{2: 2, 4: 2, 6: 5, 7: 6, 10: 7, 15: 6, 16: 6, 17: 8, 18: 8, 20: 9, 21: 9, 23: 11, 24: 12, 27: 11, 28: 9, 29: 8, 31: 7, 32: 6, 39: 2, 40: 2}

Answer 2

В зависимости от варианта использования и контекста может быть достаточно чего-то простого:

from collections import Counter
from itertools import chain

counts = Counter(chain.from_iterable(range(f, t+1) for f,t in input_intervals))
result = {k:counts[k] for k in input_numbers}

O (n * k + m), где n - количество интервалов, k - среднее размер интервала, а m - количество целых чисел.

Answer 3

Вы можете предварительно отсортировать integers и затем использовать bisect_left в нижней границе. Сортировка имеет сложность O (M * log (M)), в то время как у деления есть O (log (M)). Таким образом, у вас есть O (max (M, N) * log (M)).

import bisect
from collections import defaultdict

result = defaultdict(int)
integers = sorted(integers)
for low, high in intervals:
    index = bisect.bisect_left(integers, low)
    while index < len(integers) and integers[index] <= high:
        result[integers[index]] += 1
        index += 1