Compute intersections for each segment
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given n segments on a number line. Segment i is [startsAt[i], endsAt[i]] (inclusive), with 1 ≤ n ≤ 1e5 and 1 ≤ startsAt[i] ≤ endsAt[i] ≤ 1e9. For each segment i (0 ≤ i < n), determine how many other segments intersect it. Two segments intersect if they share at least one common point. Return an integer array counts of length n where counts[i] is the number of intersections for segment i. Design an algorithm faster than O(n^
2) (aim for O(n log n)), explain its time and space complexity, and implement a function countIntersections(int[] startsAt, int[] endsAt). Clarify how you handle equal endpoints and duplicate segments. Example: startsAt = [1, 3], endsAt = [4, 5] → counts = [1, 1] because [1,4] intersects [3,5] at points 3 and 4.
Quick Answer: This question evaluates algorithmic problem-solving, interval reasoning, and complexity-analysis skills by requiring an efficient method to count how many other segments intersect each interval while accounting for edge cases like equal endpoints and duplicate segments.
You are given n segments on a number line. Segment i is the closed interval [startsAt[i], endsAt[i]] (inclusive endpoints), with 1 <= n <= 1e5 and 1 <= startsAt[i] <= endsAt[i] <= 1e9.
For each segment i (0 <= i < n), determine how many OTHER segments intersect it. Two segments intersect if they share at least one common point on the number line (touching at a single shared endpoint counts as an intersection, since the intervals are closed). A segment never counts itself.
Return an integer array `counts` of length n, where counts[i] is the number of other segments that intersect segment i.
Aim for an O(n log n) algorithm rather than the brute-force O(n^2) pairwise scan.
Example: startsAt = [1, 3], endsAt = [4, 5] -> counts = [1, 1], because segment [1,4] and segment [3,5] share the points 3 and 4.
Constraints
- 1 <= n <= 1e5
- 1 <= startsAt[i] <= endsAt[i] <= 1e9
- Segments are closed (inclusive) intervals; touching at one shared endpoint counts as an intersection
- A segment does not intersect itself; counts[i] is over the other n-1 segments
- Identity is by index, not value: duplicate/identical segments each intersect the others
Examples
Input: ([1, 3], [4, 5])
Expected Output: [1, 1]
Explanation: Segments [1,4] and [3,5] share points 3 and 4, so each intersects exactly one other segment.
Input: ([5], [10])
Expected Output: [0]
Explanation: A single segment has no other segments to intersect.
Hints
- Counting intersections directly is awkward because the overlap condition couples both endpoints. Count the segments that do NOT intersect segment i and subtract from n-1. Two segments fail to intersect iff one lies entirely to the left of the other.
- A segment j misses segment i in exactly one of two disjoint ways: j ends strictly before i begins (endsAt[j] < startsAt[i]), or j begins strictly after i ends (startsAt[j] > endsAt[i]). These two groups cannot overlap, so count each independently and add them.
- 'How many endsAt[j] < startsAt[i]?' and 'how many startsAt[j] > endsAt[i]?' are order-statistic queries. Sort all start values and all end values once, then answer every query with a binary search (lower_bound / upper_bound). Segment i is never in its own left or right group, so query over all n values and rely on the -1 to remove self.
- Use STRICT inequalities (< and >) so segments that merely touch at a shared endpoint stay counted as intersecting, matching the inclusive-interval semantics.