Facebook Pixel

3323. Minimize Connected Groups by Inserting Interval 🔒

MediumArrayBinary SearchSortingSliding Window
Leetcode Link

Problem Description

You are given a 2D array intervals, where each intervals[i] = [start_i, end_i] represents the start and end of interval i. Additionally, you are provided an integer k. Your task is to 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 this interval, the number of connected groups in intervals is minimized.

A connected group of intervals refers to a maximal collection of intervals that, when viewed together, cover a continuous range from the smallest point to the largest point without any gaps. For example:

  • The group [[1, 2], [2, 5], [3, 3]] is connected because they cover the range from 1 to 5 without gaps.
  • Conversely, the group [[1, 2], [3, 4]] is not connected due to the gap from 2 to 3.

Your goal is to determine the minimum number of connected groups after adding the new interval.

Intuition

The core strategy to solve this problem is to minimize the number of disjoint (non-connected) intervals or groups by effectively inserting a new interval that merges as many existing groups as possible. Here’s how one can approach this:

  1. Sort and Merge: Begin by sorting the intervals by their start values. Then merge overlapping intervals to create a consolidated list of intervals or groups. This helps in understanding the current "connectivity" state of the intervals.

  2. Initial Count: Calculate the initial number of connected groups, which corresponds to the length of this merged interval array.

  3. Optimal Insertion Point: By iterating through each endpoint, determine if inserting a new interval from any current endpoint will allow merging more intervals ahead. Use a technique similar to binary search to find the first interval that won't merge with a new interval of length k appended to the current end.

  4. Update and Minimize: For each endpoint, calculate how many groups can be merged using the new interval and update the answer to reflect the minimal number of connected groups that could be achieved.

This approach efficiently reduces the number of disjoint groups by optimally utilizing the additional interval constraint of length k, leveraging sorting and binary search for performance.

Learn more about Binary Search, Sorting and Sliding Window patterns.

Solution Approach

The solution involves a few key steps that utilize sorting, merging, and binary search to effectively minimize the number of connected groups after adding a new interval.

Step 1: Sorting and Merging Intervals

  • First, sort the input intervals based on their starting points. This helps in organizing the intervals for the merging process.
  • Initialize a list merged to store merged intervals. Start by adding the first sorted interval to merged.
  • Iterate over the sorted intervals and merge overlapping intervals:
    • If the current interval does not overlap with the last interval in merged, simply append it to merged.
    • If it overlaps, extend the end of the last interval in merged to cover the current interval.
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)

Step 2: Finding Minimum Connected Groups

  • The initial number of connected groups is simply the length of merged.
  • Iterate over each interval endpoint e in merged.
  • Use binary search to find the first interval in merged that starts after e + k + 1. This marks the first point that a new interval of length up to k can connect.
  • Calculate the potential number of connected groups by considering this new interval and update the minimum answer accordingly.
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))

Step 3: Return the Result

  • Finally, return ans, which represents the minimum number of connected groups possible after optimally adding the new interval.
return ans

Key Concepts and Techniques

  • Merging Intervals: This is a common technique to handle overlapping intervals.
  • Binary Search (bisect_left): This is used to efficiently find the position of the first interval that starts after a certain point, allowing us to determine how many groups a new interval can merge.
  • Optimization with Minimum Tracking: Continuously track and update the minimum possible connected groups by evaluating each potential insertion point.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach for minimizing connected groups by adding a new interval.

Example:

Consider the intervals [[1, 2], [6, 8], [11, 15]] and k = 3. We aim to introduce one new interval [start_new, end_new] where the length end_new - start_new is at most k, to minimize the number of connected groups.

Step-by-step Solution:

  1. Sorting and Merging Intervals:

    • Start by sorting the intervals based on their start values: [ \text{Sorted intervals}: [[1, 2], [6, 8], [11, 15]] ]
    • Merge overlapping intervals:
      • Since none of these intervals overlap initially, the merged intervals remain the same: [ \text{Merged intervals}: [[1, 2], [6, 8], [11, 15]] ]

  2. Initial Count of Connected Groups:

    • The initial number of connected groups corresponds to the length of merged, which is 3.

  3. Determine Optimal Insertion Point:

    • Iterating over each endpoint e in merged and trying to see where an interval of length up to k can connect:

      • For endpoint 2: Check if [2, 5] can merge - It can't merge with any more groups.
      • For endpoint 8: Check if [8, 11] can merge - It bridges the gap between [6, 8] and [11, 15], thus reducing the number of groups.
      • For endpoint 15: Check if [15, 18] can merge - It doesn't merge more groups.

    • Use binary search (bisect_left) to optimize and find positions for possible merges efficiently.

  4. Updating the Minimum Count of Groups:

    • After evaluating each potential new interval:
      • The interval [8, 11] merges two groups—[[6, 8]] and [[11, 15]]—into one.
      • The minimal connected groups achieved is 2.

Step 3: Return the Result

  • The function returns 2, indicating that the minimum number of connected intervals after adding the new interval is 2.

Solution Implementation

1from typing import List
2from bisect import bisect_left
3
4class Solution:
5    def minConnectedGroups(self, intervals: List[List[int]], k: int) -> int:
6        # Sort the intervals based on start times
7        intervals.sort()
8
9        # Merge overlapping intervals
10        merged = [intervals[0]]
11        for start, end in intervals[1:]:
12            if merged[-1][1] < start:
13                # If the current interval does not overlap, add it to merged list
14                merged.append([start, end])
15            else:
16                # If the current interval overlaps, merge intervals by updating the end time
17                merged[-1][1] = max(merged[-1][1], end)
18
19        # Initialize the answer as the number of merged intervals
20        ans = len(merged)
21
22        # Try minimizing the number of groups using the buffer k
23        for i, (_, end) in enumerate(merged):
24            # Find the earliest starting interval that starts after end + k
25            j = bisect_left(merged, [end + k + 1, 0])
26            # Calculate the possible minimum group by excluding overlapped intervals
27            ans = min(ans, len(merged) - (j - i - 1))
28
29        return ans
30
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public int minConnectedGroups(int[][] intervals, int k) {
7        // Sort the intervals based on the start time.
8        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
9      
10        // This list will store the merged intervals.
11        List<int[]> merged = new ArrayList<>();
12        merged.add(intervals[0]); // Add the first interval as the starting point.
13      
14        // Iterate over each interval to merge overlapping ones.
15        for (int i = 1; i < intervals.length; i++) {
16            int[] currentInterval = intervals[i];
17            int[] lastMergedInterval = merged.get(merged.size() - 1);
18          
19            // Check if the current interval overlaps with the last merged interval.
20            if (lastMergedInterval[1] < currentInterval[0]) {
21                // No overlap, add current interval to merged list.
22                merged.add(currentInterval);
23            } else {
24                // Overlap, merge current interval by extending the end of the last merged interval.
25                lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
26            }
27        }
28
29        // Initialize the answer with total number of merged intervals.
30        int ans = merged.size();
31      
32        // Try connecting groups by finding suitable intervals with a gap of size k.
33        for (int i = 0; i < merged.size(); i++) {
34            int[] interval = merged.get(i);
35            // Perform a binary search to find the first interval that starts beyond the end of this interval + k.
36            int j = binarySearch(merged, interval[1] + k + 1);
37            // Update the minimum number of groups that need to stay disconnected.
38            ans = Math.min(ans, merged.size() - (j - i - 1));
39        }
40
41        return ans;
42    }
43
44    // Helper method to perform binary search on the list of merged intervals.
45    private int binarySearch(List<int[]> intervals, int x) {
46        int left = 0, right = intervals.size();
47        // Binary search to find the first interval with a start time >= x.
48        while (left < right) {
49            int mid = (left + right) >> 1;
50            if (intervals.get(mid)[0] >= x) {
51                right = mid;
52            } else {
53                left = mid + 1;
54            }
55        }
56        return left;
57    }
58}
59
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int minConnectedGroups(std::vector<std::vector<int>>& intervals, int k) {
7        // Sort the intervals by their start time.
8        std::sort(intervals.begin(), intervals.end());
9
10        // This will hold the merged intervals.
11        std::vector<std::vector<int>> merged;
12
13        // Process each interval for merging.
14        for (const auto& interval : intervals) {
15            int start = interval[0], end = interval[1];
16          
17            // If merged is empty or the last merged interval does not overlap with the current interval.
18            if (merged.empty() || merged.back()[1] < start) {
19                // Add the current interval as a new merged interval.
20                merged.emplace_back(interval);
21            } else {
22                // Merge the current interval with the last one in merged.
23                merged.back()[1] = std::max(merged.back()[1], end);
24            }
25        }
26
27        // Initialize the answer with the number of merged intervals.
28        int minGroups = merged.size();
29
30        // Iterate over each merged interval to find the minimum connected group size.
31        for (int i = 0; i < merged.size(); ++i) {
32            auto& interval = merged[i];
33
34            // Use a binary search to find the first interval that starts after the current interval plus k.
35            int j = std::lower_bound(merged.begin(), merged.end(), std::vector<int>{interval[1] + k + 1, 0}) - merged.begin();
36
37            // Calculate the potential minimum group size if intervals [i, j) are connected.
38            minGroups = std::min(minGroups, static_cast<int>(merged.size()) - (j - i - 1));
39        }
40
41        // Return the minimum number of connected groups.
42        return minGroups;
43    }
44};
45
1// Function to find the minimum number of connected groups 
2// after potentially merging nearby intervals within "k" distance.
3function minConnectedGroups(intervals: number[][], k: number): number {
4    // Sort the intervals based on the starting points.
5    intervals.sort((a, b) => a[0] - b[0]);
6
7    // Array to hold merged intervals.
8    const merged: number[][] = [];
9
10    // Merge overlapping intervals.
11    for (const interval of intervals) {
12        const [start, end] = interval;
13
14        // If merged is empty or the last merged interval ends before the current one starts,
15        // add the current interval to merged.
16        if (merged.length === 0 || merged.at(-1)![1] < start) {
17            merged.push(interval);
18        } else {
19            // Otherwise, extend the last merged interval to cover the current one.
20            merged.at(-1)![1] = Math.max(merged.at(-1)![1], end);
21        }
22    }
23
24    // Binary search function to find the position where we can start merging 
25    // additional intervals with a minimum gap of k between intervals.
26    const search = (x: number): number => {
27        let left = 0;
28        let right = merged.length;
29
30        // Perform binary search.
31        while (left < right) {
32            const mid = (left + right) >> 1;
33            if (merged[mid][0] >= x) {
34                right = mid;
35            } else {
36                left = mid + 1;
37            }
38        }
39
40        // Return the position found.
41        return left;
42    };
43
44    // Initialize the answer to the number of initially merged intervals.
45    let answer = merged.length;
46
47    // Traverse through each interval to possibly merge further based on the distance "k".
48    for (let i = 0; i < merged.length; ++i) {
49        // Find the position to initiate merging such that the interval starts after the 
50        // current interval ends plus the additional distance "k".
51        const j = search(merged[i][1] + k + 1);
52
53        // Update the answer with the minimal number of groups possible after merging.
54        answer = Math.min(answer, merged.length - (j - i - 1));
55    }
56
57    // Return the minimum number of connected groups.
58    return answer;
59}
60

Time and Space Complexity

The time complexity of the code is O(n \times \log n) because of the initial sort operation on the list of intervals, which takes O(n \times \log n), and the subsequent operations involving a loop and binary search that are O(n).

The space complexity is O(n) due to the additional space used by the merged list that stores the merged intervals.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More