We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize Connected Groups by Inserting Interval

Number: 3565

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a list of intervals and an integer k, you must add exactly one new interval (of length at most k) such that after adding it, the number of connected groups formed by the intervals is minimized. A connected group is a maximal collection of intervals that together cover a continuous range with no gaps.

Key Insights

  • First, merge the given intervals into connected groups.
  • Each connected group is represented by its overall minimum start and maximum end.
  • Gaps between adjacent groups represent the “distance” that separates them.
  • The new interval, by design, can connect consecutive groups if its length is at least the gap between them.
  • The problem boils down to finding the longest sequence of consecutive groups that can be merged using one new interval of length ≤ k.
  • Use a two‑pointer or sliding window strategy over the sorted groups to find the maximum chain that can be connected.

Space and Time Complexity

Time Complexity: O(n log n) primarily due to sorting the intervals. Space Complexity: O(n) for storing the groups (in worst-case all intervals are non-overlapping).

Solution

  1. Sort the intervals by starting time.
  2. Merge overlapping or touching intervals into connected groups.
  3. For each group, determine its start and end.
  4. Use a two-pointer (sliding window) approach over the connected groups:
    • For each starting group, try to extend the window by including subsequent groups.
    • The condition to merge groups i to j is that the new interval must cover the gap from groups[i].end to groups[j].start. In other words, the required length is groups[j].start - groups[i].end.
    • If this required length is ≤ k, the new interval could connect these groups.
    • Track the maximum number of groups that can be merged.
  5. The final answer is the total number of connected groups minus (maxChain - 1) because merging maxChain groups reduces the total count by maxChain - 1.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java.

# Python solution with line-by-line comments
def minimizeConnectedGroups(intervals, k):
    # Step 1: Sort intervals based on start time
    intervals.sort(key=lambda interval: interval[0])
    
    # Step 2: Merge overlapping intervals to form connected groups
    groups = []
    current_start, current_end = intervals[0]
    for start, end in intervals[1:]:
        if start <= current_end:  # intervals overlap or touch
            current_end = max(current_end, end)
        else:
            groups.append((current_start, current_end))
            current_start, current_end = start, end
    groups.append((current_start, current_end))
    
    # m is the number of connected groups
    m = len(groups)
    
    # Step 3: Use sliding window (two pointers) to find the maximum chain that can be merged
    max_chain = 1
    left = 0
    # For each group as a starting point
    for right in range(m):
        # Calculate required new interval length = gap from groups[left] end to groups[right] start
        while left <= right and groups[right][0] - groups[left][1] > k:
            left += 1
        # The number of groups we can merge in this window
        current_chain = right - left + 1
        max_chain = max(max_chain, current_chain)
    
    # Final minimal connected groups = total groups - (max_chain - 1)
    return m - max_chain + 1

# Example usage:
print(minimizeConnectedGroups([[1,3],[5,6],[8,10]], 3))  # Expected output: 2
print(minimizeConnectedGroups([[5,10],[1,1],[3,3]], 1))    # Expected output: 3
← Back to All Questions