Number of Intersecting Interval Pairs I - Solution & Explanation

Easy9 min read

Problem Statement

You are given a 2D integer array intervals of n elements, where intervals[i] = [start_i, end_i] represents the closed interval from start_i to end_i.

Return the number of pairs of indices (i, j) such that 0 <= i < j < n and intervals[i] and intervals[j] intersect.

Two intervals intersect if they have at least one point in common, including when they only share an endpoint.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4]]

Output: 2

Explanation:

There are 2 intersecting interval pairs:

Intervals [1, 2] and [2, 3] intersect at the point 2.
Intervals [2, 3] and [3, 4] intersect at the point 3.

Example 2:

Input: intervals = [[1,5],[2,4],[3,6]]

Output: 3

Explanation:

There are 3 intersecting interval pairs:

The intersection of [1, 5] and [2, 4] is [2, 4].
The intersection of [1, 5] and [3, 6] is [3, 5].
The intersection of [2, 4] and [3, 6] is [3, 4].

Example 3:

Input: intervals = [[1,2],[3,4],[5,6]]

Output: 0

Explanation:

There are no intersecting interval pairs. Hence, the answer is 0.

Constraints:

2 <= n == intervals.length <= 100
intervals[i] = [start_i, end_i]
0 <= start_i <= end_i <= 100

Solution

Thinking

n \le 100, so enumerating every index pair and checking intersection would pass. Two closed intervals are disjoint if and only if one right endpoint is strictly less than the other left endpoint.

Pairwise checks need both sides of that test. It is cleaner to start from \frac{n(n-1)}{2} and subtract the disjoint pairs: for each left endpoint, count how many intervals have already ended before it starts.

After sorting the left and right endpoints separately, a pointer that only moves right counts those finished intervals in one scan.

Two closed intervals [l_1, r_1] and [l_2, r_2] are disjoint if and only if r_1 < l_2 or r_2 < l_1.

The total number of pairs is \frac{n(n-1)}{2}. We count the disjoint pairs and subtract them from the total.

Sort all left endpoints and all right endpoints in ascending order. Enumerate each left endpoint s from left to right, and maintain a pointer i for the number of intervals with ends[i] < s. Those intervals are disjoint from the current one, so we subtract that count from the answer.

Each disjoint pair is counted exactly once: the interval with the smaller right endpoint is charged when we scan the other interval's left endpoint.

The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of intervals.