Skip to content

3323. Minimize Connected Groups by Inserting Interval πŸ”’

Description

You are given a 2D array intervals, where intervals[i] = [starti, endi] represents the start and the end of interval i. You are also given an integer k.

You must add exactly one new interval [startnew, endnew] to the array such that:

  • The length of the new interval, endnew - startnew, is at most k.
  • After adding, the number of connected groups in intervals is minimized.

A connected group of intervals is a maximal collection of intervals that, when considered together, cover a continuous range from the smallest point to the largest point with no gaps between them. Here are some examples:

  • A group of intervals [[1, 2], [2, 5], [3, 3]] is connected because together they cover the range from 1 to 5 without any gaps.
  • However, a group of intervals [[1, 2], [3, 4]] is not connected because the segment (2, 3) is not covered.

Return the minimum number of connected groups after adding exactly one new interval to the array.

 

Example 1:

Input: intervals = [[1,3],[5,6],[8,10]], k = 3

Output: 2

Explanation:

After adding the interval [3, 5], we have two connected groups: [[1, 3], [3, 5], [5, 6]] and [[8, 10]].

Example 2:

Input: intervals = [[5,10],[1,1],[3,3]], k = 1

Output: 3

Explanation:

After adding the interval [1, 1], we have three connected groups: [[1, 1], [1, 1]], [[3, 3]], and [[5, 10]].

 

Constraints:

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

Solutions

Thinking

We may insert one interval of length at most \(k\) to minimize the number of connected groups. With \(n \le 10^5\) we first merge overlaps, then ask how many merged pieces one bridge can join.

After merging, pieces are disjoint. From the right end \(e\) of piece \(i\), every piece whose left end is less than \(e+k+1\) can be covered by that bridge.

Binary search finds the first index \(j\) beyond the bridge; the new count is \(|\textit{merged}|-(j-i-1)\), and we keep the minimum.

First, we sort the given set of intervals \(\textit{intervals}\) by their left endpoints, then merge all overlapping intervals to obtain a new set of intervals \(\textit{merged}\).

We can then set the initial answer to the length of \(\textit{merged}\).

Next, we enumerate each interval \([\_, e]\) in \(\textit{merged}\). Using binary search, we find the first interval in \(\textit{merged}\) whose left endpoint is greater than or equal to \(e + k + 1\), and let its index be \(j\). We can then update the answer as \(\textit{ans} = \min(\textit{ans}, |\textit{merged}| - (j - i - 1))\).

Finally, we return the answer \(\textit{ans}\).

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

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

Comments