1415. Seamless Timeline
A film festival wants to run its screenings back to back on one screen. Screening i occupies the half-open time range [start, end) given by intervals[i] = [start, end) with start < end.
Return true if all the screenings can be arranged in a single order so that each one begins at exactly the minute the previous one finishes, with no idle minute and no overlap. Return false otherwise. A single screening always chains. The given array is in arbitrary order.
Hint on the contract: only the arrangement by start time can possibly work, so sort by start and compare each end with the next start. Target O(n log n) time and O(1) extra space beyond the sort.
Example 1
- Input:
- intervals = [[4,6],[0,2],[2,4]]
- Output:
- true
- Explanation:
Sorted by start the screenings are [0,2), [2,4), [4,6) and each ends where the next begins.
Example 2
- Input:
- intervals = [[0,3],[4,6]]
- Output:
- false
- Explanation:
Minute 3 is idle before the screening at 4, so the chain breaks.
Example 3
- Input:
- intervals = [[0,5],[3,8]]
- Output:
- false
- Explanation:
The two screenings overlap on [3,5), so they cannot chain.
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)