Count interval intersections
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Overview: This question evaluates understanding of interval relationships, efficient counting under large constraints, and algorithmic complexity analysis for overlapping ranges.
Constraints
- 1 <= n <= 10^5
- 1 <= start[i] <= end[i] <= 10^9
- Two segments intersect if they share at least one point, including touching at a single endpoint.
- A segment is not counted as intersecting itself.
Examples
Input: ([1, 2, 5], [3, 4, 6])
Expected Output: [1, 1, 0]
Explanation: [1,3] and [2,4] overlap (each other); [5,6] is disjoint from both.
Input: ([1], [5])
Expected Output: [0]
Explanation: Single segment has no others to intersect.
Hints
- Counting intersecting pairs directly is hard; count the complement instead. For segment i, every other segment either intersects it, lies entirely to its left (its end < start[i]), or lies entirely to its right (its start > end[i]).
- So counts[i] = (n - 1) - (# segments with end < start[i]) - (# segments with start > end[i]).
- Sort all ends and all starts once. Use binary search (bisect) to count how many ends are < start[i] and how many starts are > end[i] in O(log n) per query, giving O(n log n) overall.
- Watch the boundary: touching counts as intersecting, so use strict '<' for the left group (end < start[i]) and strict '>' for the right group (start > end[i]); equality keeps the segment in the intersecting set.