Count integers in intervals

Design Segment Tree Ordered Set

35.7% acceptance

Feb 23, 2026

621

Given an empty set of intervals, implement a data structure that can: Add an interval to the set of intervals. Count the number of integers that are present in at least one interval. Implement the CountIntervals class: CountIntervals() Initializes the object with an empty set of intervals. void add(int left, int right) Adds the interval [left, right] to the set of intervals. int count() Returns the number of integers that are present in at least one interval. Note that an interval [left, right] denotes all the integers x where left <= x <= right.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeMap;

pub struct CountIntervals {
  intervals: BTreeMap<i32, i32>, // start -> end
  cnt: i32,
}

impl CountIntervals {
  pub fn new() -> Self {
    CountIntervals { intervals: BTreeMap::new(), cnt: 0 }
  }

  pub fn add(&mut self, left: i32, right: i32) {
    let mut new_l = left;
    let mut new_r = right;

    // Check interval that starts just before left and may overlap
    if let Some((&k, &v)) = self.intervals.range(..left).next_back() {
      if v >= left {
        new_l = k;
        new_r = new_r.max(v);
        self.cnt -= v - k + 1;
        self.intervals.remove(&k);
      }
    }

    // Merge all intervals starting in [left, new_r]
    loop {
      let entry = self.intervals.range(left..=new_r).next().map(|(&k, &v)| (k, v));
      match entry {
        Some((k, v)) => {
          new_r = new_r.max(v);
          self.cnt -= v - k + 1;
          self.intervals.remove(&k);
        }
        None => break,
      }
    }

    self.intervals.insert(new_l, new_r);
    self.cnt += new_r - new_l + 1;
  }

  pub fn count(&self) -> i32 {
    self.cnt
  }
}