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