跳转至

4056. 统计相交区间对 I

来源第 520 场周赛 Q1难度简单分数1161

题目描述

给你一个包含 n 个元素的二维整数数组 intervals，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi 的 闭区间 。

返回满足 0 <= i < j < n，且 intervals[i] 与 intervals[j] 相交 的下标对 (i, j) 的数量。

如果两个区间至少有一个公共点，则称它们 相交。仅共享一个端点的情况也视为相交。

 

示例 1：

输入： intervals = [[1,2],[2,3],[3,4]]

输出： 2

解释：

共有 2 对相交区间：

  • 区间 [1, 2] 和 [2, 3] 在点 2 处相交。
  • 区间 [2, 3] 和 [3, 4] 在点 3 处相交。

示例 2：

输入： intervals = [[1,5],[2,4],[3,6]]

输出： 3

解释：

共有 3 对相交区间：

  • [1, 5] 和 [2, 4] 的交集为 [2, 4]。
  • [1, 5] 和 [3, 6] 的交集为 [3, 5]。
  • [2, 4] 和 [3, 6] 的交集为 [3, 4]。

示例 3：

输入： intervals = [[1,2],[3,4],[5,6]]

输出： 0

解释：

不存在相交的区间对。因此，答案为 0。

 

提示：

  • 2 <= intervals.length <= 100
  • intervals[i] == [starti, endi]
  • 0 <= starti <= endi <= 100

解法

方法一：排序 + 双指针

思考

\(n \le 100\)，枚举全部下标对判断是否相交就能通过。两个闭区间不相交，当且仅当其中一个的右端点严格小于另一个的左端点。

直接枚举要对每个对写两端判断。从 \(\frac{n(n-1)}{2}\) 里减去不相交对更干净：对每个左端点，统计有多少个区间已经在它开始之前结束。

左右端点分别排序后，指针只向右移动，一次扫描就能得到每个起点对应的不相交个数。

两个闭区间 \([l_1, r_1]\)、 \([l_2, r_2]\) 不相交，当且仅当 \(r_1 < l_2\) 或 \(r_2 < l_1\)。

区间对的总数为 \(\frac{n(n-1)}{2}\)。我们统计不相交的对数，再从总数中减去。

将所有左端点、右端点分别升序排列。从左到右枚举每个左端点 \(s\)，用指针 \(i\) 维护满足 \(\textit{ends}[i] < s\) 的区间个数，这些区间与当前区间不相交，从答案中减去。

每个不相交对恰好被统计一次：右端点更小的那个区间，会在扫描另一个区间的左端点时被计入。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是区间的数量。

 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;
}

评论