Problem 334893 · medium · Phase 03 Linear Management & Searching

Count Overlapping Meeting Pairs

sorting · intervals · bisect · sort-then-scan

Each meeting is a pair [start, end] with start < end. Two meetings overlap when they share at least one moment of time strictly inside both, i.e. max(start1, start2) < min(end1, end2). A meeting that starts exactly when another ends does not overlap it.

Return the number of unordered pairs of meetings that overlap.

Examples

Input:  meetings = [[1, 3], [2, 5], [4, 6], [3, 4]]
Output: 3
Explanation: The overlapping pairs are ([1,3],[2,5]), ([2,5],[4,6]) and ([2,5],[3,4]).
             [1,3] and [3,4] only touch, so they do not count.

Constraints

  • 0 <= len(meetings) <= 10**5
  • 0 <= start < end <= 10**9
  • Target complexity: O(n log n). A nested loop over all pairs is too slow.

Goals

  • Sort intervals by start so that all later overlaps come from later starts
  • Count, for each meeting, how many later meetings start before it ends
  • Use binary search instead of a nested loop
Starting Python…