Нужно посчитать максимальное число пользователей, одновременно смотревших
игровой стрим. Каждый пользователь подключился в момент In и отключился в
момент Out: он смотрит стрим в моменты In ≤ t < Out. Значит, если один
отключился ровно тогда, когда подключился другой, одновременно они не
смотрели. Сессия с In == Out — пустая, её никто не видел.
type Session struct {
In, Out int
}
// MaxViewers возвращает максимальное число одновременных зрителей.
func MaxViewers(sessions []Session) int
Примеры
[] → 0
[(101,105), (105,110)] → 1
[(101,105), (100,101), (104,105)] → 2
[(101,110), (105,106), (102,103), (107,108)] → 2
[(101,102), (101,110), (104,109), (108,115),
(105,106), (108,116)] → 4
Ограничения
0 ≤ len(sessions) ≤ 10⁶, сессии не упорядочены, 0 ≤ In ≤ Out ≤ 10⁹.- Входной слайс менять нельзя.
- Ожидается O(n log n). Попарная проверка пересечений — O(n²) — не уложится.