Skip to content

2276. Count Integers in Intervals 👍

  • Time:
    • Constructor: $O(1)$
    • add(left: int, right: int): $O(\log n)$
    • count(): $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class CountIntervals {
 public:
  void add(int left, int right) {
    while (isOverlapped(left, right)) {
      auto it = prev(intervals.upper_bound(right));
      const int l = it->first;
      const int r = it->second;
      left = min(left, l);
      right = max(right, r);
      intervals.erase(l);
      cnt -= r - l + 1;
    }

    intervals[left] = right;
    cnt += right - left + 1;
  }

  int count() {
    return cnt;
  }

 private:
  map<int, int> intervals;
  int cnt = 0;

  bool isOverlapped(int left, int right) {
    auto it = intervals.upper_bound(right);
    return it != intervals.begin() && prev(it)->second >= left;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class CountIntervals {
  public void add(int left, int right) {
    while (isOverlapped(left, right)) {
      final int l = intervals.floorKey(right);
      final int r = intervals.get(l);
      left = Math.min(left, l);
      right = Math.max(right, r);
      intervals.remove(l);
      count -= r - l + 1;
    }

    intervals.put(left, right);
    count += right - left + 1;
  }

  public int count() {
    return count;
  }

  private TreeMap<Integer, Integer> intervals = new TreeMap<>();
  private int count = 0;

  private boolean isOverlapped(int left, int right) {
    // L := the maximum number <= end
    Integer l = intervals.floorKey(right);
    return l != null && intervals.get(l) >= left;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from sortedcontainers import SortedDict


class CountIntervals:
  def __init__(self):
    self.intervals = SortedDict()
    self.cnt = 0

  def add(self, left: int, right: int) -> None:
    while self._isOverlapped(left, right):
      i = self.intervals.bisect_right(right) - 1
      l, r = self.intervals.popitem(i)
      left = min(left, l)
      right = max(right, r)
      self.cnt -= r - l + 1

    self.intervals[left] = right
    self.cnt += right - left + 1

  def count(self) -> int:
    return self.cnt

  def _isOverlapped(self, left: int, right: int) -> bool:
    i = self.intervals.bisect_right(right)
    return i > 0 and self.intervals.peekitem(i - 1)[1] >= left