# Count Integers in Intervals
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-integers-in-intervals)
Canonical: https://scaleengineer.com/dsa/problems/count-integers-in-intervals
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Segment Tree, Ordered Set
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Databricks](https://scaleengineer.com/companies/databricks)
---
## 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`.

# Approaches
## Merge Intervals on `count()`
This approach involves storing all added intervals in a simple list. The `add` operation is very fast, as it just appends the new interval. The main work is done in the `count` method. When `count` is called, we take all the intervals stored so far, sort them, and then apply the standard 'Merge Intervals' algorithm to find the set of disjoint intervals. Finally, we sum the lengths of these merged intervals to get the total count of unique integers.
**Time:** - `add(left, right)`: O(1)
- `count()`: O(N log N), where N is the number of intervals. The sorting step dominates the time complexity. · **Space:** O(N), where N is the number of intervals added. This space is used to store the intervals themselves and for the temporary list during the merge process.
**Pros:** The logic is straightforward to understand, based on the classic 'Merge Intervals' problem.; The `add` operation is extremely fast (O(1)).
**Cons:** The `count()` operation is very slow, with a time complexity of O(N log N), where N is the number of intervals added.; This approach is inefficient if `count()` is called frequently, as it repeatedly sorts and merges the entire list of intervals from scratch.; It is likely to result in a 'Time Limit Exceeded' (TLE) error for problem constraints involving a large number of calls.
### Explanation
### Data Structure
We use a `java.util.List<int[]>` to store the intervals. The `add` operation is trivial, but the `count` operation bears the computational load.

### `add(left, right)`
This method simply adds a new integer array `new int[]{left, right}` to our list. Its complexity is O(1).

### `count()`
This is where the core logic resides. To find the total number of unique integers, we must first resolve any overlaps. This is a classic 'Merge Intervals' problem.
1.  First, we sort all the intervals in our list based on their starting points.
2.  Then, we iterate through the sorted intervals and merge any that overlap.
3.  An interval `[s1, e1]` overlaps with `[s2, e2]` if `s2 <= e1` (assuming the list is sorted by start times).
4.  The merged interval will have a start of `s1` and an end of `max(e1, e2)`.
5.  After producing a new list of disjoint, merged intervals, we can calculate the total count by summing up the size of each interval (`right - left + 1`).

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.LinkedList;

class CountIntervals {
    private List<int[]> intervals;

    public CountIntervals() {
        intervals = new ArrayList<>();
    }

    public void add(int left, int right) {
        intervals.add(new int[]{left, right});
    }

    public int count() {
        if (intervals.isEmpty()) {
            return 0;
        }

        // Sort intervals based on the start point
        Collections.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        LinkedList<int[]> merged = new LinkedList<>();
        for (int[] interval : intervals) {
            // if the list of merged intervals is empty or if the current
            // interval does not overlap with the previous, simply append it.
            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
                merged.add(interval.clone()); // Use clone to avoid modifying original list if needed
            } else {
                // otherwise, there is overlap, so we merge the current and previous
                // intervals.
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }
        
        // To optimize subsequent calls, we can replace the old list with the merged one.
        this.intervals = new ArrayList<>(merged);

        int totalCount = 0;
        for (int[] interval : merged) {
            totalCount += (interval[1] - interval[0] + 1);
        }
        return totalCount;
    }
}
```
### Algorithm
- **Data Structure**: Use a `List<int[]>` to store all intervals as they are added.
- **`add(left, right)`**:
  - Simply append the new interval `[left, right]` to the list.
- **`count()`**:
  1. Check if the list of intervals is empty. If so, return 0.
  2. Create a copy of the interval list to avoid modifying the original.
  3. Sort the copied list of intervals based on their start points.
  4. Initialize a new list, `mergedIntervals`, to store the result of merging.
  5. Add the first interval from the sorted list to `mergedIntervals`.
  6. Iterate through the rest of the sorted intervals:
     - If the current interval overlaps with the last interval in `mergedIntervals`, merge them by updating the end point of the last interval.
     - Otherwise, the intervals are disjoint, so add the current interval to `mergedIntervals`.
  7. After iterating through all intervals, `mergedIntervals` will contain a set of disjoint intervals.
  8. Calculate the total count by summing the lengths (`right - left + 1`) of all intervals in `mergedIntervals`.

## Online Merging with a `TreeMap`
This optimal approach maintains a set of disjoint intervals at all times. By doing so, the total count of integers can also be maintained incrementally. When a new interval is added, we find all existing intervals that it overlaps with, merge them into a single new interval, and then update the set of disjoint intervals and the total count. A `TreeMap` in Java is an excellent data structure for this, as it keeps the intervals sorted by their start times and allows for efficient searching, insertion, and deletion.
**Time:** - `add(left, right)`: O(k * log N), where N is the number of disjoint intervals and k is the number of intervals merged. The amortized time complexity is O(log N).
- `count()`: O(1). · **Space:** O(N), where N is the maximum number of disjoint intervals. In the worst case, N is the number of `add` calls if no intervals ever merge.
**Pros:** Highly efficient, passing all constraints with ease.; The `count()` operation is instantaneous (O(1)).; The `add()` operation is very fast on average, with an amortized time complexity of O(log N).; Space efficient, as it only stores disjoint intervals.
**Cons:** The implementation is more complex than simpler approaches.; Requires a good understanding of `TreeMap` and its operations like `floorEntry`.
### Explanation
### Data Structure
We use a `TreeMap<Integer, Integer>` to store the disjoint intervals, where the key is the interval's start and the value is its end. This keeps the intervals sorted by their start times. We also maintain an integer variable, `count`, to store the total number of integers covered by these intervals.

### `add(left, right)`
This is the core of the algorithm. Instead of recalculating the total count from scratch, we update it incrementally. When adding `[left, right]`: 
1. We identify all existing intervals in our `TreeMap` that overlap with `[left, right]`.
2. An existing interval `[l, r]` overlaps with a new interval `[new_l, new_r]` if `l <= new_r` and `r >= new_l`.
3. We can find these overlapping intervals efficiently. We start by looking for an interval `[l, r]` where `l <= right`. The `TreeMap.floorEntry(right)` method is perfect for this. 
4. We then iterate backwards, merging all overlapping intervals into one large interval. For each interval we merge, we remove it from the map and subtract its length from our running `count`.
5. Finally, we add the newly formed, larger interval to the map and add its length to `count`.

### `count()`
Since we maintain the `count` variable with every `add` operation, this method simply returns the current value of `count`, making it an O(1) operation.

```java
import java.util.Map;
import java.util.TreeMap;

class CountIntervals {
    private TreeMap<Integer, Integer> intervals;
    private int count;

    public CountIntervals() {
        intervals = new TreeMap<>();
        count = 0;
    }

    public void add(int left, int right) {
        int start = left;
        int end = right;

        // Find an entry whose start is less than or equal to the new interval's end.
        Map.Entry<Integer, Integer> entry = intervals.floorEntry(end);

        // Iterate backwards through all intervals that overlap with the new one.
        while (entry != null && entry.getValue() >= start) {
            int l = entry.getKey();
            int r = entry.getValue();

            // Merge the overlapping interval with our new interval.
            start = Math.min(start, l);
            end = Math.max(end, r);

            // Remove the old interval and subtract its length from the total count.
            intervals.remove(l);
            this.count -= (r - l + 1);

            // Move to the previous entry to check for more overlaps.
            entry = intervals.floorEntry(start - 1);
        }

        // Add the new merged interval to the map and its length to the count.
        intervals.put(start, end);
        this.count += (end - start + 1);
    }

    public int count() {
        return this.count;
    }
}
```
### Algorithm
- **Data Structure**: Use a `TreeMap<Integer, Integer>` to store disjoint intervals, mapping start points to end points. Maintain an integer `count` for the total size.
- **`CountIntervals()`**:
  - Initialize an empty `TreeMap` and set `count = 0`.
- **`add(left, right)`**:
  1. Define the interval to be added as `[start, end]`, initially `[left, right]`.
  2. Find all existing intervals in the `TreeMap` that overlap with `[start, end]`.
  3. An efficient way to do this is to start with `entry = map.floorEntry(end)` and iterate backwards as long as the entry's interval overlaps with `[start, end]`.
  4. For each overlapping interval `[l, r]` found:
     - Merge it by updating `start = min(start, l)` and `end = max(end, r)`.
     - Remove the old interval `[l, r]` from the `TreeMap`.
     - Decrement the total `count` by the length of the removed interval (`r - l + 1`).
  5. After all merges are complete, insert the new, combined interval `[start, end]` into the `TreeMap`.
  6. Increment the total `count` by the length of this new interval (`end - start + 1`).
- **`count()`**:
  - Simply return the pre-calculated `count` variable.

# Solutions
### Java

```java
class Node { Node left ; Node right ; int l ; int r ; int mid ; int v ; int add ; public Node ( int l , int r ) { this . l = l ; this . r = r ; this . mid = ( l + r ) >> 1 ; } } class SegmentTree { private Node root = new Node ( 1 , ( int ) 1 e9 + 1 ); public SegmentTree () { } public void modify ( int l , int r , int v ) { modify ( l , r , v , root ); } public void modify ( int l , int r , int v , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v = node . r - node . l + 1 ; node . add = v ; return ; } pushdown ( node ); if ( l <= node . mid ) { modify ( l , r , v , node . left ); } if ( r > node . mid ) { modify ( l , r , v , node . right ); } pushup ( node ); } public int query ( int l , int r ) { return query ( l , r , root ); } public int query ( int l , int r , Node node ) { if ( l > r ) { return 0 ; } if ( node . l >= l && node . r <= r ) { return node . v ; } pushdown ( node ); int v = 0 ; if ( l <= node . mid ) { v += query ( l , r , node . left ); } if ( r > node . mid ) { v += query ( l , r , node . right ); } return v ; } public void pushup ( Node node ) { node . v = node . left . v + node . right . v ; } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node ( node . l , node . mid ); } if ( node . right == null ) { node . right = new Node ( node . mid + 1 , node . r ); } if ( node . add != 0 ) { Node left = node . left , right = node . right ; left . add = node . add ; right . add = node . add ; left . v = left . r - left . l + 1 ; right . v = right . r - right . l + 1 ; node . add = 0 ; } } } class CountIntervals { private SegmentTree tree = new SegmentTree (); public CountIntervals () { } public void add ( int left , int right ) { tree . modify ( left , right , 1 ); } public int count () { return tree . query ( 1 , ( int ) 1 e9 ); } } /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals obj = new CountIntervals(); * obj.add(left,right); * int param_2 = obj.count(); */
```

### CPP

```cpp
class Node { public: Node ( int l , int r ) : l ( l ) , r ( r ) , mid (( l + r ) / 2 ) , v ( 0 ) , add ( 0 ) , left ( nullptr ) , right ( nullptr ) {} int l , r , mid , v , add ; Node * left ; Node * right ; }; class SegmentTree { public: SegmentTree () : root ( new Node ( 1 , 1000000001 )) {} void modify ( int l , int r , int v , Node * node = nullptr ) { if ( node == nullptr ) { node = root ; } if ( l > r ) { return ; } if ( node -> l >= l && node -> r <= r ) { node -> v = node -> r - node -> l + 1 ; node -> add = v ; return ; } pushdown ( node ); if ( l <= node -> mid ) { modify ( l , r , v , node -> left ); } if ( r > node -> mid ) { modify ( l , r , v , node -> right ); } pushup ( node ); } int query ( int l , int r , Node * node = nullptr ) { if ( node == nullptr ) { node = root ; } if ( l > r ) { return 0 ; } if ( node -> l >= l && node -> r <= r ) { return node -> v ; } pushdown ( node ); int v = 0 ; if ( l <= node -> mid ) { v += query ( l , r , node -> left ); } if ( r > node -> mid ) { v += query ( l , r , node -> right ); } return v ; } private: Node * root ; void pushup ( Node * node ) { node -> v = node -> left -> v + node -> right -> v ; } void pushdown ( Node * node ) { if ( node -> left == nullptr ) { node -> left = new Node ( node -> l , node -> mid ); } if ( node -> right == nullptr ) { node -> right = new Node ( node -> mid + 1 , node -> r ); } if ( node -> add != 0 ) { Node * left = node -> left ; Node * right = node -> right ; left -> add = node -> add ; right -> add = node -> add ; left -> v = left -> r - left -> l + 1 ; right -> v = right -> r - right -> l + 1 ; node -> add = 0 ; } } }; class CountIntervals { public: CountIntervals () {} void add ( int left , int right ) { tree . modify ( left , right , 1 ); } int count () { return tree . query ( 1 , 1000000000 ); } private: SegmentTree tree ; }; /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */
```

### Python

```python
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()
```