Count interval intersections
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
For a list of n segments, where each segment i has start[i] and end[i], compute for every segment the count of other segments that intersect it (share at least one common point). Return an array counts where counts[i] is the number of intersections for segment i.
Constraints: 1 ≤ n ≤ 10^5, 1 ≤ start[i] ≤ end[i] ≤ 10^9.
Quick Answer: This question evaluates understanding of interval relationships, efficient counting under large constraints, and algorithmic complexity analysis for overlapping ranges.
For a list of `n` segments where segment `i` spans `[start[i], end[i]]`, compute for every segment the number of OTHER segments that intersect it (share at least one common point, i.e. they overlap or merely touch at an endpoint). Return an array `counts` where `counts[i]` is the intersection count for segment `i`.
Two segments `[a, b]` and `[c, d]` intersect iff `a <= d` and `c <= b`.
Example: `start = [1, 2, 5]`, `end = [3, 4, 6]` -> `[1, 1, 0]`. Segment 0 `[1,3]` overlaps segment 1 `[2,4]`; segment 1 also overlaps segment 0; segment 2 `[5,6]` overlaps neither.
Constraints: `1 <= n <= 10^5`, `1 <= start[i] <= end[i] <= 10^9`. An O(n^2) pairwise check is too slow for the upper bound; aim for O(n log n).
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.