Skip to content

4056. Number of Intersecting Interval Pairs I

SourceWeekly Contest 520 Q1DifficultyEasyRating1161

Description

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

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] = [starti, endi]
  • 0 <= starti <= endi <= 100

Solutions

Solution 1: Sorting + Two Pointers

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 \(\textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countIntersectingIntervals(self, intervals: list[list[int]]) -> int:
        n = len(intervals)
        starts = sorted(s for s, _ in intervals)
        ends = sorted(e for _, e in intervals)
        ans = n * (n - 1) // 2
        i = 0
        for start in starts:
            while i < n and ends[i] < start:
                i += 1
            ans -= i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int countIntersectingIntervals(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int ans = n * (n - 1) / 2;
        int i = 0;
        for (int start : starts) {
            while (i < n && ends[i] < start) {
                i++;
            }
            ans -= i;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countIntersectingIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<int> starts(n), ends(n);
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        int ans = n * (n - 1) / 2;
        int i = 0;
        for (int start : starts) {
            while (i < n && ends[i] < start) {
                i++;
            }
            ans -= i;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func countIntersectingIntervals(intervals [][]int) int {
    n := len(intervals)
    starts := make([]int, n)
    ends := make([]int, n)
    for i, p := range intervals {
        starts[i] = p[0]
        ends[i] = p[1]
    }
    slices.Sort(starts)
    slices.Sort(ends)
    ans := n * (n - 1) / 2
    i := 0
    for _, start := range starts {
        for i < n && ends[i] < start {
            i++
        }
        ans -= i
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function countIntersectingIntervals(intervals: number[][]): number {
    const n = intervals.length;
    const starts = intervals.map(([s]) => s).sort((a, b) => a - b);
    const ends = intervals.map(([, e]) => e).sort((a, b) => a - b);
    let ans = (n * (n - 1)) / 2;
    let i = 0;
    for (const start of starts) {
        while (i < n && ends[i] < start) {
            i++;
        }
        ans -= i;
    }
    return ans;
}

Comments