Compute intersections for each segment

Q: Compute intersections for each segment

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute intersections for each segment

Overview

Comments (0)