Set intersection size at least two

Array Greedy Sorting

57.9% acceptance

Feb 21, 2026

1121

110

You are given a 2D integer array intervals where intervals[i] = [starti, endi] represents all the integers from starti to endi inclusively. A containing set is an array nums where each interval from intervals has at least two integers in nums. For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets. Return the minimum possible size of a containing set.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

/*
 * You are given a 2D integer array intervals where intervals[i] = [starti, endi] represents all the integers from starti to endi inclusively.
 * A containing set is an array nums where each interval from intervals has at least two integers in nums.
 * For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.
 * Return the minimum possible size of a containing set.
 * Example 1:
 * Input: intervals = [[1,3],[3,7],[8,9]]
 * Output: 5
 * Explanation: let nums = [2, 3, 4, 8, 9].
 * It can be shown that there cannot be any containing array of size 4.
 * Example 2:
 * Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
 * Output: 3
 * Explanation: let nums = [2, 3, 4].
 * It can be shown that there cannot be any containing array of size 2.
 * Example 3:
 * Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
 * Output: 5
 * Explanation: let nums = [1, 2, 3, 4, 5].
 * It can be shown that there cannot be any containing array of size 4.
 * Constraints:
 * 1 <= intervals.length <= 3000
 * intervals[i].length == 2
 * 0 <= starti < endi <= 108
 */
impl Solution {
  pub fn intersection_size_two(mut intervals: Vec<Vec<i32>>) -> i32 {
    intervals.sort_by(|a, b| a[1].cmp(&b[1]).then(b[0].cmp(&a[0])));
    let mut chosen: Vec<i32> = vec![];
    for interval in &intervals {
      let (lo, hi) = (interval[0], interval[1]);
      let cnt = chosen.iter().filter(|&&x| x >= lo && x <= hi).count();
      if cnt == 0 {
        chosen.push(hi - 1);
        chosen.push(hi);
      } else if cnt == 1 {
        chosen.push(hi);
      }
    }
    chosen.len() as i32
  }
}