Minimize Connected Groups by Inserting Interval

Problem

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.

Examples

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 <= 10^5
• intervals[i] == [starti, endi]
• 1 <= starti <= endi <= 10^9
• 1 <= k <= 10^9

Solution

Method 1 – Greedy Merge with Sorting and Gap Analysis

Intuition

To minimize the number of connected groups after inserting a new interval, we should target the largest gaps between existing groups. By sorting intervals and analyzing the gaps, we can optimally place the new interval (of length ≤ k) to cover as many gaps as possible, thus merging groups.

Approach

1. Sort intervals by start.
2. Merge overlapping intervals to find all connected groups.
3. Identify gaps between groups (gap = next group's start - previous group's end).
4. Sort gaps in ascending order.
5. Place the new interval to cover as many consecutive gaps as possible, with total gap length ≤ k.
6. The minimum number of groups is original groups minus the number of covered gaps.

Code

C++

class Solution {
public:
    int minimizeGroups(vector<vector<int>>& intervals, int k) {
        sort(intervals.begin(), intervals.end());
        vector<pair<int, int>> merged;
        for (auto& it : intervals) {
            if (merged.empty() || merged.back().second < it[0])
                merged.push_back({it[0], it[1]});
            else
                merged.back().second = max(merged.back().second, it[1]);
        }
        vector<int> gaps;
        for (int i = 1; i < merged.size(); ++i)
            gaps.push_back(merged[i].first - merged[i-1].second);
        sort(gaps.begin(), gaps.end());
        int ans = merged.size();
        int sum = 0;
        for (int g : gaps) {
            if (sum + g > k) break;
            sum += g;
            ans--;
        }
        return ans;
    }
};

Go

func minimizeGroups(intervals [][]int, k int) int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    merged := [][]int{}
    for _, it := range intervals {
        if len(merged) == 0 || merged[len(merged)-1][1] < it[0] {
            merged = append(merged, []int{it[0], it[1]})
        } else {
            merged[len(merged)-1][1] = max(merged[len(merged)-1][1], it[1])
        }
    }
    gaps := []int{}
    for i := 1; i < len(merged); i++ {
        gaps = append(gaps, merged[i][0]-merged[i-1][1])
    }
    sort.Ints(gaps)
    ans, sum := len(merged), 0
    for _, g := range gaps {
        if sum+g > k { break }
        sum += g
        ans--
    }
    return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }

Java

class Solution {
    public int minimizeGroups(int[][] intervals, int k) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] it : intervals) {
            if (merged.isEmpty() || merged.get(merged.size()-1)[1] < it[0])
                merged.add(new int[]{it[0], it[1]});
            else
                merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1], it[1]);
        }
        List<Integer> gaps = new ArrayList<>();
        for (int i = 1; i < merged.size(); i++)
            gaps.add(merged.get(i)[0] - merged.get(i-1)[1]);
        Collections.sort(gaps);
        int ans = merged.size(), sum = 0;
        for (int g : gaps) {
            if (sum + g > k) break;
            sum += g;
            ans--;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun minimizeGroups(intervals: Array<IntArray>, k: Int): Int {
        intervals.sortBy { it[0] }
        val merged = mutableListOf<IntArray>()
        for (it in intervals) {
            if (merged.isEmpty() || merged.last()[1] < it[0])
                merged.add(intArrayOf(it[0], it[1]))
            else
                merged.last()[1] = maxOf(merged.last()[1], it[1])
        }
        val gaps = mutableListOf<Int>()
        for (i in 1 until merged.size)
            gaps.add(merged[i][0] - merged[i-1][1])
        gaps.sort()
        var ans = merged.size; var sum = 0
        for (g in gaps) {
            if (sum + g > k) break
            sum += g
            ans--
        }
        return ans
    }
}

Python

def minimize_connected_groups(intervals: list[list[int]], k: int) -> int:
    intervals.sort()
    merged = []
    for it in intervals:
        if not merged or merged[-1][1] < it[0]:
            merged.append(it[:])
        else:
            merged[-1][1] = max(merged[-1][1], it[1])
    gaps = [merged[i][0] - merged[i-1][1] for i in range(1, len(merged))]
    gaps.sort()
    ans, sum_gap = len(merged), 0
    for g in gaps:
        if sum_gap + g > k:
            break
        sum_gap += g
        ans -= 1
    return ans

Rust

impl Solution {
    pub fn minimize_connected_groups(mut intervals: Vec<Vec<i32>>, k: i32) -> i32 {
        intervals.sort();
        let mut merged = vec![];
        for it in intervals {
            if merged.is_empty() || merged.last().unwrap()[1] < it[0] {
                merged.push(it.clone());
            } else {
                merged.last_mut().unwrap()[1] = merged.last().unwrap()[1].max(it[1]);
            }
        }
        let mut gaps: Vec<i32> = (1..merged.len()).map(|i| merged[i][0] - merged[i-1][1]).collect();
        gaps.sort();
        let mut ans = merged.len() as i32;
        let mut sum = 0;
        for g in gaps {
            if sum + g > k { break; }
            sum += g;
            ans -= 1;
        }
        ans
    }
}

TypeScript

class Solution {
    minimizeConnectedGroups(intervals: number[][], k: number): number {
        intervals.sort((a, b) => a[0] - b[0]);
        const merged: number[][] = [];
        for (const it of intervals) {
            if (!merged.length || merged[merged.length-1][1] < it[0])
                merged.push([...it]);
            else
                merged[merged.length-1][1] = Math.max(merged[merged.length-1][1], it[1]);
        }
        const gaps = [];
        for (let i = 1; i < merged.length; ++i)
            gaps.push(merged[i][0] - merged[i-1][1]);
        gaps.sort((a, b) => a - b);
        let ans = merged.length, sum = 0;
        for (const g of gaps) {
            if (sum + g > k) break;
            sum += g;
            ans--;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log n), for sorting and merging intervals.
• 🧺 Space complexity: O(n), for storing merged intervals and gaps.