1416. Longest Busy Block
A rehearsal studio logs each booking as a half-open range intervals[i] = [start, end), in no particular order. Bookings that overlap, or that touch because one end equals another start, count as one continuous busy block.
Merge the bookings into maximal busy blocks and return the length, end - start, of the longest block as an integer. Blocks separated by even one idle unit stay separate. Two identical bookings simply form one block.
Sort by start, sweep once, extend the current block while the next start is at most the current end, and keep the best length. Target O(n log n) time and O(1) extra space.
Example 1
- Input:
- intervals = [[1,4],[3,6],[10,12]]
- Output:
- 5
- Explanation:
The first two merge into [1,6) of length 5, longer than [10,12) of length 2.
Example 2
- Input:
- intervals = [[0,2],[2,5],[7,8]]
- Output:
- 5
- Explanation:
Touching ranges join: [0,2) and [2,5) form [0,5) of length 5.
Example 3
- Input:
- intervals = [[5,9]]
- Output:
- 4
- Explanation:
A single booking is its own block of length 4.
Constraints
- 1 ≤ n ≤ 1000, where n is the number of intervals
- 0 ≤ start < end ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(1)