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).
First, we sort the given set of intervals intervals by their left endpoints, then merge all overlapping intervals to obtain a new set of intervals merged.
We can then set the initial answer to the length of merged.
Next, we enumerate each interval [_, e] in merged. Using binary search, we find the first interval in 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 ans = min(ans, |merged| - (j - i - 1)).
Finally, we return the answer ans.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of intervals.
Python
Java
C++
Go
TypeScript
| 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 |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,307 views views
Watch 9 more video solutions →Practice Minimize Connected Groups by Inserting Interval with our built-in code editor and test cases.
Practice on FleetCode