Интервалы обработки

Question

Как найти количество интервалов, которые попадают в данный диапазон. например, Позвольте мне объяснить, что существует диапазон [1,10], а предоставленные интервалы - (1,3), (1,8), (2,4), (2,5), (2,3), (3,9), (3,8), (3,6) и попросить выяснить количество интервалов, которые падают между диапазонами [1,5], ответ равен 4. Это четыре [(1,3), (2,4), (2,5), (2,3)], которые попадают в диапазон [1,5]. так же, как если бы они были Range [1, N], и я предоставляю вам интервалы, то как узнать, сколько интервалов в заданном диапазоне. Какая из них самая сложная задача для каждого запроса?

Answer 1

O (n). Вы не можете сделать лучше. По крайней мере, вы должны ответить, что каждый интервал действителен для запроса, который является O (n). Вы можете получить O (п), просто перебирая список, чтобы проверить, если query_min < = interval_min & & query_max < = interval_max