1373. Earliest Clash
A rental desk accepts reservations in the order they are listed in bookings. Reservation i holds the item for the half-open range bookings[i] = [start, end). Two reservations clash when they share a stretch of positive length; one that ends exactly when another starts is fine.
Return the smallest index j such that reservation j clashes with at least one reservation of smaller index i < j. Return -1 if no two reservations clash. Index 0 can never be the answer.
One route: the prefix up to index j is clash-free exactly when, after sorting it by start, each end is at most the next start, and this property only gets worse as the prefix grows, so binary search on j. Any O(n log^2 n) or better approach is intended; n is at most 1000.
Example 1
- Input:
- bookings = [[5,8],[1,3],[7,10],[3,5]]
- Output:
- 2
- Explanation:
Booking 2 = [7,10) overlaps booking 0 = [5,8) on [7,8), and no earlier booking clashes.
Example 2
- Input:
- bookings = [[0,2],[2,4],[4,6]]
- Output:
- -1
- Explanation:
Each booking starts exactly when the previous one ends, so nothing clashes.
Example 3
- Input:
- bookings = [[1,10],[2,3]]
- Output:
- 1
- Explanation:
Booking 1 lies inside booking 0, so index 1 is the first clash.
Constraints
- 1 ≤ n ≤ 1000, where n is the number of bookings
- 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^2 n)
- Space
- O(n)