Watch 10 video solutions for Minimize Connected Groups by Inserting Interval, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by Ashish Pratap Singh has 1,002,307 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
endnew - startnew, is at most k.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:
[[1, 2], [2, 5], [3, 3]] is connected because together they cover the range from 1 to 5 without any gaps.[[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 <= 109Problem Overview: You are given several intervals that may form multiple disconnected groups. You can insert one additional interval. The goal is to place this interval so that it connects as many existing groups as possible, minimizing the final number of connected components.
Approach 1: Brute Force Gap Merging (O(n^2) time, O(1) space)
Start by sorting intervals by their starting position using sorting. Compute the gaps between consecutive merged intervals. Try placing the new interval so that it bridges different combinations of gaps and simulate how many groups merge. For every starting interval, expand forward while the inserted interval can still cover the span needed to connect them. This approach works conceptually but becomes quadratic because each starting point may scan many following intervals.
Approach 2: Sorting + Binary Search (O(n log n) time, O(n) space)
Sort intervals first, then merge overlapping ones to determine the true connected groups. After merging, compute the gaps between consecutive groups. If an inserted interval can cover multiple consecutive gaps, those groups collapse into one component. For each group i, use binary search to find the farthest group j such that the total distance from the end of group i to the start of group j can be covered by the inserted interval. The number of groups merged equals j - i. Track the maximum merge possible and subtract it from the original group count.
Approach 3: Sorting + Sliding Window (O(n log n) time, O(n) space)
After sorting and merging intervals, treat the problem as covering consecutive gaps with a single interval of fixed reach. Maintain a window of groups and track the span between the first group's end and the current group's start. If that span exceeds the allowed coverage, move the left pointer forward. This two-pointer technique from sliding window keeps the largest set of groups that can be connected by one inserted interval. The result is the total groups minus the maximum window size reduction.
Recommended for interviews: The expected solution is Sorting + Binary Search or a sliding window after sorting. The brute-force gap simulation demonstrates understanding of how intervals merge, but the optimized method shows you can translate the problem into a range search over sorted intervals and reduce it to O(n log n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Gap Merging | O(n^2) | O(1) | Useful for understanding how interval gaps combine and verifying correctness on small inputs |
| Sorting + Binary Search | O(n log n) | O(n) | Best general solution when intervals must be sorted and the farthest connectable group is searched efficiently |
| Sorting + Sliding Window | O(n log n) | O(n) | Clean implementation after sorting; ideal when consecutive gaps are processed with two pointers |