Count interval intersections

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.

Count Interval Intersections

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.

Hints

1. 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]).
2. So counts[i] = (n - 1) - (# segments with end < start[i]) - (# segments with start > end[i]).
3. 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.
4. 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.