Find maximal uncovered ranges

Array Sorting

49.4% acceptance

Mar 31, 2026

You are given an integer n which is the length of a 0-indexed array nums, and a 0-indexed 2D-array ranges, which is a list of sub-ranges of nums (sub-ranges may overlap). Each row ranges[i] has exactly 2 cells: ranges[i][0], which shows the start of the ith range (inclusive) ranges[i][1], which shows the end of the ith range (inclusive) These ranges cover some cells of nums and leave some cells uncovered. Your task is to find all of the uncovered ranges with maximal length. Return a 2D-array answer of the uncovered ranges, sorted by the starting point in ascending order. By all of the uncovered ranges with maximal length, we mean satisfying two conditions: Each uncovered cell should belong to exactly one sub-range There should not exist two ranges (l1, r1) and (l2, r2) such that r1 + 1 = l2

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_maximal_uncovered_ranges(n: i32, ranges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if ranges.is_empty() {
      return vec![vec![0, n - 1]];
    }
    let mut ranges = ranges;
    ranges.sort_by_key(|r| (r[0], r[1]));
    let mut merged: Vec<[i32; 2]> = Vec::new();
    for r in &ranges {
      if let Some(last) = merged.last_mut() {
        if r[0] <= last[1] + 1 {
          last[1] = last[1].max(r[1]);
        } else {
          merged.push([r[0], r[1]]);
        }
      } else {
        merged.push([r[0], r[1]]);
      }
    }
    let mut result = Vec::new();
    let mut prev_end: i32 = -1;
    for m in &merged {
      if prev_end + 1 < m[0] {
        result.push(vec![prev_end + 1, m[0] - 1]);
      }
      prev_end = m[1];
    }
    if prev_end < n - 1 {
      result.push(vec![prev_end + 1, n - 1]);
    }
    result
  }
}