Здравствуйте.

Сильно в фоновом режиме прохожу курс института Сан-Диего по алгоритмам.
Так сказать гешефт прикрываю

Вот четкая формулировка: даны начала отрезков (массив), конец отрезков (массив)
и точки (массив). Для каждой точки посчитать число интервалов, куда она входит.

И конкретно туплю -- у меня время решения (не знаю единиц) что-то типа 500 из 20.
где туплю, но туплю, видимо, сильно. В общем вот:

#скачал из интернетов -- возвращает число меньших эл-во чем заданный в отсортированном массиве
def binarySearchCount(arr: List[Tuple[int, int]],item, key):
    left = 0
    n = len(arr)
    right = n - 1
    count = 0

    while left <= right:

        mid = (right + left) // 2

        # Check if middle element is
        # less than or equal to key
        if arr[mid][item] < key:

            # At least (mid ) elements are there
            # whose values are less than
            # or equal to key
            count = mid
            left = mid + 1

        # If key is smaller, ignore right half
        else:
            right = mid - 1

    return count


def fast_count_segments(starts: List[int], ends: List[int], points: List[int]):
   
    cnt = [0] * len(points)
   
    tups_sort_by_end = [(starts[i], ends[i]) for i in range(len(ends))]
    tups_sort_by_start = [(starts[i], ends[i]) for i in range(len(ends))]

    # сортирую по началу и концу nlog(n)
    tups_sort_by_end.sort(key=lambda tup: tup[1])
    tups_sort_by_start.sort(key=lambda tup: tup[0])

    l_s = len(tups_sort_by_end)
    d = {}
    for i in range(len(points)):

        if points[i] in d:
            cnt[i] = d[points[i]]
            continue

        # смотрю, где меньше итераций(к началу или к концу)
        idx_e = binarySearchCount(tups_sort_by_end, 1, points[i])
        idx_s = binarySearchCount(tups_sort_by_start, 0, points[i])

        # лежит во всех интервалах, готово, идем дальше
        if idx_s == l_s and idx_e == 0:
            cnt[i] = l_s
        else:
            if idx_s == idx_e:
                for j in range(idx_e, l_s):
                    if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
                        cnt[i] += 1
            else:
                if idx_s > l_s - idx_e:
                    # к концу быстрее
                    for j in range(idx_e, l_s):
                        if tups_sort_by_end[j][0] <= points[i] <= tups_sort_by_end[j][1]:
                            cnt[i] += 1
                else:
                    # к началу быстрее
                    for j in range(0, idx_s + 1):
                        if tups_sort_by_start[j][0] <= points[i] <= tups_sort_by_start[j][1]:
                            cnt[i] += 1

        d[points[i]] = cnt[i]

    return cnt

Глава называется Divide and Conquer, ничего лучше чем отсортировать, бинарным поиском отсечь лишнее, а дальше
по всем оставшимся пройти и проверить, я не придумал. Однако в одном из тестов по времени я сильно не укладываюсь,
причем сами данные не показывают....

ЧЯДНТ? Думается, что можно как-то избавиться от циклов после (дважды)бинарного поиска...