Welcome to Subscribe On Youtube
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 mostk. - After adding, the number of connected groups in
intervalsis 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 <= 105intervals[i] == [starti, endi]1 <= starti <= endi <= 1091 <= k <= 109
Solutions
Solution 1: Sorting + Binary Search
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.
-
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; } } -
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; } }; -
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 -
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 } -
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; }