Minimize Connected Groups by Inserting Interval

Minimize Connected Groups by Inserting Interval - Problem

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

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

The length of the new interval, end_new - start_new, 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.

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.

Input & Output

Example 1 — Bridge Two Groups

$ Input: intervals = [[1,3],[5,7]], k = 2

› Output: 1

💡 Note: Original has 2 groups: [1,3] and [5,7]. Gap between them is (3,5) with size 2. We can add [3,5] (length=2≤k) to connect both groups into one.

Example 2 — Cannot Bridge Fully

$ Input: intervals = [[1,2],[6,8]], k = 2

› Output: 2

💡 Note: Gap is (2,6) with size 4 > k=2. Best we can do is add [2,4] or [4,6], but this creates 3 total groups. Better to add [1,1] (extends first group) keeping 2 groups.

Example 3 — Already Connected

$ Input: intervals = [[1,5],[3,7]], k = 1

› Output: 1

💡 Note: Intervals overlap, so already 1 connected group. Adding any new interval keeps it at 1 group minimum.

Constraints

0 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
-10⁹ ≤ start_i ≤ end_i ≤ 10⁹
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Groups

Original intervals form separate connected groups

Find Gap

Identify gap between groups that can be bridged

Bridge Gap

Add new interval to connect groups and minimize total count

Key Takeaway

🎯 Key Insight: The optimal strategy is to identify gaps between separate groups and bridge them with the new interval to maximize group merging

Asked in

G Google 35 M Microsoft 28 a Amazon 22

The key insight is to sort intervals, merge overlapping ones to identify connected groups, then find gaps between groups that can be bridged with a new interval of length ≤ k. Best approach is sort-first with time O(n log n) and space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Sort and Find Best Gap	O(n log n)	O(n)	Sort intervals, identify gaps between connected groups, find optimal gap to fill
Brute Force - Try All Possible Intervals	O(R² × n log n)	O(n)	Try every possible new interval of length ≤ k and count connected groups

Optimized - Sort and Find Best Gap — Algorithm Steps

Step 1: Sort intervals and merge overlapping ones to get connected groups
Step 2: Identify gaps between consecutive groups
Step 3: For each gap, check if we can bridge it with interval of length ≤ k
Step 4: Return original group count minus maximum bridgeable groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Merge

Create connected groups from overlapping intervals

Find Gaps

Identify spaces between groups

Bridge Gap

Place new interval to connect groups optimally

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    int *ia = *(int**)a;
    int *ib = *(int**)b;
    return ia[0] - ib[0];
}

int solution(int** intervals, int n, int k) {
    if (n == 0) return 1;
    
    // Sort intervals
    qsort(intervals, n, sizeof(int*), compare);
    
    // Merge overlapping intervals
    int** merged = malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        merged[i] = malloc(2 * sizeof(int));
    }
    
    merged[0][0] = intervals[0][0];
    merged[0][1] = intervals[0][1];
    int mergedCount = 1;
    
    for (int i = 1; i < n; i++) {
        if (intervals[i][0] <= merged[mergedCount-1][1]) {
            if (intervals[i][1] > merged[mergedCount-1][1]) {
                merged[mergedCount-1][1] = intervals[i][1];
            }
        } else {
            merged[mergedCount][0] = intervals[i][0];
            merged[mergedCount][1] = intervals[i][1];
            mergedCount++;
        }
    }
    
    // If only one group, we can't reduce further
    if (mergedCount == 1) {
        // Free memory
        for (int i = 0; i < n; i++) {
            free(merged[i]);
        }
        free(merged);
        return 1;
    }
    
    // Find gaps between consecutive groups
    int minGroups = mergedCount;
    
    for (int i = 0; i < mergedCount - 1; i++) {
        int gapStart = merged[i][1];
        int gapEnd = merged[i + 1][0];
        int gapSize = gapEnd - gapStart;
        
        // If we can bridge this gap with an interval of length ≤ k
        if (gapSize <= k) {
            if (mergedCount - 1 < minGroups) {
                minGroups = mergedCount - 1;
            }
        } else {
            if (k >= 0) {
                if (mergedCount - 1 < minGroups) {
                    minGroups = mergedCount - 1;
                }
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(merged[i]);
    }
    free(merged);
    
    return minGroups;
}

int main() {
    int** intervals = malloc(100 * sizeof(int*));
    int n = 0;
    int k;
    
    // Read intervals
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse [[a,b],[c,d]] format - simplified
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            intervals[n] = malloc(2 * sizeof(int));
            intervals[n][0] = strtol(ptr, &ptr, 10);
            while (*ptr == ',' || *ptr == ' ') ptr++;
            intervals[n][1] = strtol(ptr, &ptr, 10);
            n++;
        }
        ptr++;
    }
    
    scanf("%d", &k);
    
    int result = solution(intervals, n, k);
    printf("%d\n", result);
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(intervals[i]);
    }
    free(intervals);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting intervals takes O(n log n), then single pass through gaps takes O(n)

⚡ Linearithmic

Space Complexity

O(n)

Space for storing merged intervals and gap information

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Sort and Find Best Gap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler