102. Busiest Moment
A museum logs each visitor group as a pair [a, b] in intervals: the group is inside during every whole minute from min(a, b) to max(a, b), inclusive, with the two minutes listed in either order. Two groups whose time ranges share even a single minute are inside at the same time at that minute.
Find the busiest minute, that is, the integer minute during which the largest number of groups are inside, and return that largest number of groups present together. If intervals is empty, return 0. You only need the count, not the minute itself.
Example 1
- Input:
- intervals = [[1,4],[3,6],[5,8]]
- Output:
- 2
- Explanation:
At minutes 3 and 4 the first two groups overlap, and at minutes 5 and 6 the last two do; nobody sees three at once, so the answer is 2.
Example 2
- Input:
- intervals = [[2,2],[2,2],[9,7]]
- Output:
- 2
- Explanation:
The two single-minute groups both occupy minute 2, while the third group lasts from minute 7 to 9, so the answer is 2.
Constraints
- 0 ≤ intervals.length ≤ 100000
- intervals[i].length == 2
- 0 ≤ intervals[i][0], intervals[i][1] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)