Non overlapping intervals

Array Dynamic Programming Greedy Sorting

56.7% acceptance

Jan 13, 2026

9081

256

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn erase_overlap_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {
    if intervals.is_empty() {
      return 0;
    }
    
    intervals.sort_by_key(|interval| interval[1]);
    
    let mut count = 0;
    let mut end = intervals[0][1];
    
    for i in 1..intervals.len() {
      if intervals[i][0] < end {
        count += 1;
      } else {
        end = intervals[i][1];
      }
    }
    
    count
  }
}