Количество интервалов, содержащих данную точку запроса

Question

Я знаю, что подобный вопрос существует здесь .У меня такой же вопрос, что у меня N интервалов (некоторые, возможно, перекрываются, некоторые даже одинаковые).Затем задаются запросы Q-точки, и мне нужно указать, сколько интервалов содержит эту точку.

Я попытался разработать свой алгоритм, отсортировав массив конечных точек, а затем подсчитал число перекрывающихся интервалов с помощью трюка +1, -1как уже упоминалось в ответе.Но что делать после бинарного поиска?Потому что это не всегда тот случай, когда соответствующий индекс массива префиксных сумм является ответом.

e.g. 
Intervals are : [1,4] [5,7] [6,10] [7,13]
sorted end point array : [1,4,5,6,7,7,10,13]
+1/-1 array : [1,-1,1,1,1,-1,-1,-1]
prefix sum array : [1,0,1,2,3,2,1,0]

Query : 10
my algorithm gives 1 (corresponding prefix array)
but actual ans should be 2.

Как мне исправить мой алгоритм?

Answer 1

Проблема в том, что ваши интервалы [] вместо [), и ответ, вероятно, был сделан для последнего.Сначала преобразуйте свои конечные индексы в значение -1. ​​

После этого + "сжатия" повторяющихся координат вы должны иметь:

 points = [1,5,6,7,8,11,14]
 sums = [1,0,1,1,-1,-1,-1]
 accumulated = [1,1,2,3,2,1,0]

Затем для запроса, если запрос points [max] возвращают 0. Если нет, то бинарный поиск по точкам для получения индекса, и ответ лежит на накопленном [index].

Answer 2

Нет хороших ответов на вопрос, который вы связали, поэтому:

Первый:

1. Поместите позиции входа и выхода каждого интервала в отдельные массивы.(если вы используете закрытые интервалы, то позиция выхода - это конечная позиция + 1, т. е. в [4,6], вход - 4, выход - 7.
2. Сортировка массивов.

Затем для каждой точки p:

1. Двоичный поиск в массиве записей, чтобы найти количество позиций входа <= p. </li>
2. Двоичный поиск в массиве выхода, чтобы найтиколичество выходных позиций <= p. </li>
3. Число интервалов, содержащих точку: entry_count - exit_count

Обратите внимание, что число позиций <= p является индексом первогоelement> p. См .: Где в моем коде ошибка для выполнения бинарного поиска? , чтобы помочь вам правильно выполнить поиск.

Например:

Intervals: [1,4], [5,7], [6,10], [7,13]
Entry positions: [1,5,6,7]
Exit positions: [5,8,11,14]
Entry positions <= 6:  3
Exit positions <= 6: 1
Intervals that contains 6:  3-1 = 2