A meeting room receives n reservations, each a half-open interval [start, end) with start < end. Two reservations overlap if they share at least one instant — formally, if max(start_i, start_j) < min(end_i, end_j). Reservations that merely touch (one ends exactly where another begins) do not overlap. Count the number of unordered pairs of reservations that overlap.
Line 1: an integer n.
Next n lines: two integers start and end describing one reservation (start < end).
A single integer: the number of overlapping unordered pairs.
Example 1
Input
3 1 4 2 5 3 6
Expected
3
Explanation
All three pairs overlap ([1,4)&[2,5), [1,4)&[3,6), [2,5)&[3,6)), so the count is 3.
Example 2
Input
3 1 2 2 3 3 4
Expected
0
Explanation
Consecutive reservations only touch and never share an instant, so no pair overlaps: 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →