跳转至

3323. 通过插入区间最小化连通组 🔒

题目描述

给定一个 2 维数组 intervals，其中 intervals[i] = [starti, endi] 表示区间 i 的开头和结尾。另外还给定一个整数 k。

你必须向数组 恰好添加一个 新的区间 [startnew, endnew] 使得：

  • 新区间的长度，endnew - startnew 最多为 k。
  • 在添加之后，intervals 中 连通组 的数量 最少。

区间的 连通组 是一起覆盖了从最小点到最大点的连续范围，中间没有间隙的区间的最大集合。下面是一些例子：

  • 区间组 [[1, 2], [2, 5], [3, 3]] 是连通的，因为它们一起覆盖了 1 到 5 的范围，中间没有任何间隔。
  • 然而，区间组 [[1, 2], [3, 4]] 不是连通的，因为 (2, 3) 段没有被覆盖。

返回在数组 恰好添加一个 新区间后，连通组的 最小 数量。

 

示例 1：

输入：intervals = [[1,3],[5,6],[8,10]], k = 3

输出：2

解释：

在添加区间 [3, 5] 后，我们有两个连通组：[[1, 3], [3, 5], [5, 6]] 和 [[8, 10]]。

示例 2:

输入：intervals = [[5,10],[1,1],[3,3]], k = 1

输出：3

解释：

在添加区间 [1, 1] 后，我们有三个连通组：[[1, 1], [1, 1]]，[[3, 3]]，和 [[5, 10]]。

 

提示：

  • 1 <= intervals.length <= 105
  • intervals[i] == [starti, endi]
  • 1 <= starti <= endi <= 109
  • 1 <= k <= 109

解法

方法一：排序 + 二分查找

首先，我们对给定的区间集合 $\textit{intervals}$ 按照区间的左端点进行排序，然后合并所有相交的区间，得到一个新的区间集合 $\textit{merged}$。

那么我们可以将初始答案设为 $\textit{merged}$ 的长度。

接下来，我们枚举 $\textit{merged}$ 中的每一个区间 $[_, e]$，我们可以通过二分查找，在 $\textit{merged}$ 中找到第一个左端点大于等于 $e + k + 1$ 的区间，设其下标为 $j$，那么我们可以将答案更新，即 $\textit{ans} = \min(\textit{ans}, |\textit{merged}| - (j - i - 1))$。

最终，我们返回答案 $\textit{ans}$ 即可。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minConnectedGroups(self, intervals: List[List[int]], k: int) -> int:
        intervals.sort()
        merged = [intervals[0]]
        for s, e in intervals[1:]:
            if merged[-1][1] < s:
                merged.append([s, e])
            else:
                merged[-1][1] = max(merged[-1][1], e)
        ans = len(merged)
        for i, (_, e) in enumerate(merged):
            j = bisect_left(merged, [e + k + 1, 0])
            ans = min(ans, len(merged) - (j - i - 1))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int minConnectedGroups(int[][] intervals, int k) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            int[] last = merged.get(merged.size() - 1);
            if (last[1] < interval[0]) {
                merged.add(interval);
            } else {
                last[1] = Math.max(last[1], interval[1]);
            }
        }

        int ans = merged.size();
        for (int i = 0; i < merged.size(); i++) {
            int[] interval = merged.get(i);
            int j = binarySearch(merged, interval[1] + k + 1);
            ans = Math.min(ans, merged.size() - (j - i - 1));
        }

        return ans;
    }

    private int binarySearch(List<int[]> nums, int x) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums.get(mid)[0] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 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 minConnectedGroups(vector<vector<int>>& intervals, int k) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (const auto& interval : intervals) {
            int s = interval[0], e = interval[1];
            if (merged.empty() || merged.back()[1] < s) {
                merged.emplace_back(interval);
            } else {
                merged.back()[1] = max(merged.back()[1], e);
            }
        }
        int ans = merged.size();
        for (int i = 0; i < merged.size(); ++i) {
            auto& interval = merged[i];
            int j = lower_bound(merged.begin(), merged.end(), vector<int>{interval[1] + k + 1, 0}) - merged.begin();
            ans = min(ans, (int) merged.size() - (j - i - 1));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minConnectedGroups(intervals [][]int, k int) int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    merged := [][]int{}
    for _, interval := range intervals {
        s, e := interval[0], interval[1]
        if len(merged) == 0 || merged[len(merged)-1][1] < s {
            merged = append(merged, interval)
        } else {
            merged[len(merged)-1][1] = max(merged[len(merged)-1][1], e)
        }
    }
    ans := len(merged)
    for i, interval := range merged {
        j := sort.Search(len(merged), func(j int) bool { return merged[j][0] >= interval[1]+k+1 })
        ans = min(ans, len(merged)-(j-i-1))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function minConnectedGroups(intervals: number[][], k: number): number {
    intervals.sort((a, b) => a[0] - b[0]);
    const merged: number[][] = [];
    for (const interval of intervals) {
        const [s, e] = interval;
        if (merged.length === 0 || merged.at(-1)![1] < s) {
            merged.push(interval);
        } else {
            merged.at(-1)![1] = Math.max(merged.at(-1)![1], e);
        }
    }
    const search = (x: number): number => {
        let [l, r] = [0, merged.length];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (merged[mid][0] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    let ans = merged.length;
    for (let i = 0; i < merged.length; ++i) {
        const j = search(merged[i][1] + k + 1);
        ans = Math.min(ans, merged.length - (j - i - 1));
    }
    return ans;
}

评论