Метод сканирующей прямой для интервалов: что это
Коротко
Метод сканирующей прямой для интервалов: каждый интервал превращается в два события: начало (+1) и конец (-1). События сортируются по времени (при равенстве конец раньше начала для полуоткрытых интервалов), проход с накопленной суммой даёт число одновременных интервалов в каждой точке.
Определение
Каждый интервал превращается в два события: начало (+1) и конец (-1). События сортируются по времени (при равенстве конец раньше начала для полуоткрытых интервалов), проход с накопленной суммой даёт число одновременных интервалов в каждой точке. O(n log n).
Вопросы по теме с собеседований
Запомните, а не прочитайте
В тренажёре карточка вернётся, когда начнёт забываться. А билеты по Алгоритмы проверят, что термин понятен в деле.