Overlap pairs
MediumOnline Assessment
Count how many pairs of reservations overlap.
Each reservation is a half-open interval [start, end) with start < end: it occupies time from start up to, but not including, end. Two reservations overlap if they share a positive amount of time. Reservations that merely touch (one ends exactly when the other starts) do not overlap. Identical reservations are separate reservations and overlap each other. Count each unordered pair once.
Input: reservations, a list of [start, end] pairs of integers.
Output: an integer, the number of overlapping pairs. Fewer than two reservations gives 0.
An O(n log n) approach exists; inputs are large enough that checking every pair will be too slow.
Example 1
- Input:
- [[[1,4],[3,6],[4,5]]]
- Output:
- 2
- Explanation
- [1, 4) overlaps [3, 6) (they share time 3 to 4), and [3, 6) overlaps [4, 5). [1, 4) and [4, 5) only touch at 4, so they do not count. Total: 2.
Example 2
- Input:
- [[[0,10],[2,3],[5,8],[7,9],[9,12]]]
- Output:
- 5
- Explanation
- [0, 10) overlaps the four others: [2, 3), [5, 8), [7, 9) and [9, 12) (it covers time 9 to 10). [5, 8) overlaps [7, 9). [7, 9) and [9, 12) only touch. Total: 4 + 1 = 5.
Example 3
- Input:
- [[[0,2],[0,2],[2,3]]]
- Output:
- 1
- Explanation
- The two identical [0, 2) reservations overlap each other (1 pair). Each only touches [2, 3), which adds nothing. Total: 1.
Constraints
0 <= reservations.length <= 100,0000 <= start < end <= 1,000,000