Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2276.html

2276. Count Integers in Intervals

• Difficulty: Hard.
• Related Topics: Design, Segment Tree, Ordered Set.
• Similar Questions: Merge Intervals, Insert Interval, Data Stream as Disjoint Intervals, My Calendar III.

Problem

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.

  Example 1:

Input
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
Output
[null, null, null, 6, null, 8]

Explanation
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals. 
countIntervals.add(2, 3);  // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count();    // return 6
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8);  // add [5, 8] to the set of intervals.
countIntervals.count();    // return 8
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 5 and 6 are present in the interval [5, 8].
                           // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
                           // the integers 9 and 10 are present in the interval [7, 10].

  Constraints:

• 1 <= left <= right <= 109

• At most 105 calls in total will be made to add and count.

• At least one call will be made to count.

Solution

• Java
• C++
• Python

• class CountIntervals {
      private final TreeMap<Integer, Integer> map;
      private int count;
  
      public CountIntervals() {
          map = new TreeMap<>();
          map.put(-1, -1);
          map.put(1_000_000_001, 1_000_000_001);
          count = 0;
      }
  
      public void add(int left, int right) {
          Map.Entry<Integer, Integer> item =
                  map.floorEntry(left).getValue() < left
                          ? map.ceilingEntry(left)
                          : map.floorEntry(left);
          while (item.getKey() <= right) {
              left = Math.min(left, item.getKey());
              right = Math.max(right, item.getValue());
              count -= item.getValue() - item.getKey() + 1;
              map.remove(item.getKey());
              item = map.ceilingEntry(item.getKey());
          }
  
          map.put(left, right);
          count += right - left + 1;
      }
  
      public int count() {
          return count;
      }
  }
  
  /**
   * Your CountIntervals object will be instantiated and called as such:
   * CountIntervals obj = new CountIntervals();
   * obj.add(left,right);
   * int param_2 = obj.count();
   */
  

• Todo
  

• class Node:
      def __init__(self):
          self.tag = 0
          self.tot = 0
          self.left = None
          self.right = None
  
      def update(self, l, r, a, b):
          if self.tag == 1:
              return
          mid = (a + b) >> 1
          if l == a and r == b:
              self.tag = 1
              self.tot = b - a + 1
              return
          if not self.left:
              self.left = Node()
          if not self.right:
              self.right = Node()
          if mid >= l:
              self.left.update(l, min(mid, r), a, mid)
          if mid + 1 <= r:
              self.right.update(max(mid + 1, l), r, mid + 1, b)
          self.tag = 0
          self.tot = self.left.tot + self.right.tot
  
  
  class CountIntervals:
      def __init__(self):
          self.tree = Node()
  
      def add(self, left: int, right: int) -> None:
          self.tree.update(left, right, 0, 1000000010)
  
      def count(self) -> int:
          return self.tree.tot
  
  
  # Your CountIntervals object will be instantiated and called as such:
  # obj = CountIntervals()
  # obj.add(left,right)
  # param_2 = obj.count()
  
  ############
  
  # 2276. Count Integers in Intervals
  # https://leetcode.com/problems/count-integers-in-intervals
  
  from sortedcontainers import SortedList
  ​
  class CountIntervals:
  ​
      def __init__(self):
          self.sl = SortedList()
          self.res = 0
          
      def add(self, left: int, right: int) -> None:
          def overlap(l1, r1, l2, r2):
              lo = max(l1, l2)
              hi = min(r1, r2)
              
              return hi >= lo
  ​
          i = j = self.sl.bisect_left((left, -1))
          
          if i - 1 >= 0 and self.sl[i - 1][1] >= left:
              i -= 1
          
          while j < len(self.sl) and overlap(left, right, *self.sl[j]):
              j += 1
  ​
          for k in range(j - 1, i - 1, -1):
              L, R = self.sl[k]
              left = min(left, L)
              right = max(right, R)
              self.res -= R - L + 1
              del self.sl[k]
          
          self.res += right - left + 1
          self.sl.add((left, right))
  ​
      def count(self) -> int:
          return self.res
          
  ​
  ​
  # Your CountIntervals object will be instantiated and called as such:
  # obj = CountIntervals()
  # obj.add(left,right)
  # param_2 = obj.count()
  
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions