Minimize Connected Groups by Inserting Interval Solution in Java

Language Options

Problem Description

So, you think you can just throw a bunch of intervals together and expect them to play nice? Well, think again! The problem at hand is to minimize the number of connected groups of intervals by inserting new intervals. Imagine you’re at a party where everyone is mingling, but there are a few awkward groups standing alone. Your job is to make sure everyone is connected, even if it means playing the role of the social butterfly and inserting a few new intervals to bridge the gaps.

In more technical terms, given a list of intervals and a value k, you need to determine the minimum number of connected groups you can achieve by inserting intervals of length k.

Code Solution


class Solution {
  public int minConnectedGroups(int[][] intervals, int k) {
    int mergedIntervals = 0;
    int maxMergedIntervals = 0;

    intervals = merge(intervals);

    int i = 0;
    for (int[] interval : intervals) {
      final int end = interval[1];
      while (i < intervals.length && end + k >= intervals[i][0]) {
        ++mergedIntervals;
        ++i;
      }
      --mergedIntervals; // Exclude intervals[i].
      maxMergedIntervals = Math.max(maxMergedIntervals, mergedIntervals);
    }

    return intervals.length - maxMergedIntervals;
  }

  // Same as 56. Merge Intervals
  public int[][] merge(int[][] intervals) {
    List res = new ArrayList<>();
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    for (int[] interval : intervals)
      if (res.isEmpty() || res.get(res.size() - 1)[1] < interval[0])
        res.add(interval);
      else
        res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], interval[1]);
    return res.toArray(int[][] ::new);
  }
}

Approach Explanation

The code begins by merging overlapping intervals using a helper function. Once the intervals are merged, it iterates through them to count how many can be connected based on the given k. The goal is to maximize the number of merged intervals, and the final answer is derived by subtracting this maximum from the total number of intervals.

Time and Space Complexity

Time Complexity: O(n log n) due to the sorting of intervals, where n is the number of intervals.
Space Complexity: O(n) for storing the merged intervals.

Real-World Example

Imagine you’re organizing a series of events in a community center. Each event has a start and end time, and you want to ensure that there are no gaps longer than k minutes between events. If there are gaps, you might need to schedule a quick coffee break (insert an interval) to keep everyone engaged. The solution helps you figure out the minimum number of breaks needed to keep the events connected.