Здравствуйте, Sharov, Вы писали:

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

Подсчитывай интервалы, в которые НЕ входит заданная точка:
— отрезки, находящиеся полностью левее точки p (конец отрезка < p)
— отрезки, находящиеся полностью правее точки p (p < начало отрезка)
В остальные отрезки точка входит. Их количество — общее количество отрезков минус количество "ненужных" отрезков.

Каждый из этих пунктов делается бинарным поиском (если нужен "Divide and conquer") по отсортированному массиву начал и концов отрезков.
Сложность алгоритма O(N*logM) (N точек, M-отрезков)

Этот же подход можно использовать и для реализации за O(N+M). Здесь отсутствует необходимость применять бинарный поиск:
— отсортировать все искомые точки по возрастанию
— по мере прохождения по искомым точкам двигать указатели в отсортированных массивах начал и концов отрезков

Здравствуйте, Sharov, Вы писали:

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

Подсчитывай интервалы, в которые НЕ входит заданная точка:
— отрезки, находящиеся полностью левее точки p (конец отрезка < p)
— отрезки, находящиеся полностью правее точки p (p < начало отрезка)
Точка входит в остальные отрезки. Ответ = общее количество отрезков минус количество "ненужных" отрезков.

Каждый из этих пунктов делается бинарным поиском по отсортированному массиву начал и концов отрезков.
Сложность алгоритма O(N*logM) (N точек, M-отрезков). Это если нужен "Divide and conquer"

Этот же подход можно использовать и для реализации за O(N+M). Здесь отсутствует необходимость применять бинарный поиск:
— отсортировать все искомые точки по возрастанию
— по мере прохождения по искомым точкам двигать указатели в отсортированных массивах начал и концов отрезков