Minimize connected groups by inserting interval

Array Binary Search Sliding Window Sorting

50.3% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_connected_groups(intervals: Vec<Vec<i32>>, k: i32) -> i32 {
    let mut intervals = intervals;
    intervals.sort_unstable();

    let mut merged: Vec<(i32, i32)> = Vec::new();
    for iv in &intervals {
      let (s, e) = (iv[0], iv[1]);
      if let Some(last) = merged.last_mut() {
        if s <= last.1 {
          last.1 = last.1.max(e);
          continue;
        }
      }
      merged.push((s, e));
    }

    let m = merged.len();
    if m <= 1 {
      return m as i32;
    }

    let mut max_bridged = 0;
    for i in 0..m - 1 {
      let target = merged[i].1 as i64 + k as i64;
      let mut lo = i + 1;
      let mut hi = m - 1;
      let mut best = i;
      while lo <= hi {
        let mid = (lo + hi) / 2;
        if merged[mid].0 as i64 <= target {
          best = mid;
          lo = mid + 1;
        } else {
          if mid == 0 { break; }
          hi = mid - 1;
        }
      }
      max_bridged = max_bridged.max(best - i);
    }

    (m - max_bridged) as i32
  }
}