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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


    
    
    **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 <= 10^9
  • At most 105 calls in total will be made to add and count.
  • At least one call will be made to count.

Solution

Method 1 – Ordered Set / Interval Merging

Intuition

To efficiently add intervals and count the total number of unique integers covered, we can maintain a sorted list of non-overlapping intervals. When adding a new interval, we merge it with any overlapping or adjacent intervals. The count is the sum of the lengths of all intervals.

Approach

  1. Store intervals as a sorted list of non-overlapping intervals.
  2. To add a new interval:
    • Find all intervals that overlap or are adjacent to the new interval.
    • Merge them into a single interval.
    • Replace the old intervals with the merged one.
  3. To count, sum the lengths of all intervals.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class CountIntervals {
    set<pair<int, int>> s;
    int total = 0;
public:
    CountIntervals() {}
    void add(int l, int r) {
        auto it = s.lower_bound({l, 0});
        if (it != s.begin()) --it;
        while (it != s.end() && it->first <= r) {
            if (it->second < l) { ++it; continue; }
            l = min(l, it->first);
            r = max(r, it->second);
            total -= it->second - it->first + 1;
            it = s.erase(it);
        }
        s.insert({l, r});
        total += r - l + 1;
    }
    int count() { return total; }
};
1

// Not practical in Go without ordered set, use TreeMap in Java or set in C++/Python.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class CountIntervals {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    int total = 0;
    public CountIntervals() {}
    public void add(int l, int r) {
        Integer start = map.floorKey(l);
        if (start == null) start = map.ceilingKey(l);
        while (start != null && start <= r) {
            int end = map.get(start);
            if (end < l) { start = map.higherKey(start); continue; }
            l = Math.min(l, start);
            r = Math.max(r, end);
            total -= end - start + 1;
            map.remove(start);
            start = map.ceilingKey(l);
        }
        map.put(l, r);
        total += r - l + 1;
    }
    public int count() { return total; }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.TreeMap
class CountIntervals {
    private val map = TreeMap<Int, Int>()
    private var total = 0
    fun add(l: Int, r: Int) {
        var start = map.floorKey(l) ?: map.ceilingKey(l)
        while (start != null && start <= r) {
            val end = map[start]!!
            if (end < l) { start = map.higherKey(start); continue }
            l = minOf(l, start)
            r = maxOf(r, end)
            total -= end - start + 1
            map.remove(start)
            start = map.ceilingKey(l)
        }
        map[l] = r
        total += r - l + 1
    }
    fun count() = total
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from bisect import bisect_left, bisect_right
class CountIntervals:
    def __init__(self):
        self.intervals = []
        self.total = 0
    def add(self, l: int, r: int) -> None:
        i = bisect_left(self.intervals, [l, -float('inf')])
        if i > 0 and self.intervals[i-1][1] >= l-1:
            i -= 1
        new_l, new_r = l, r
        remove = []
        while i < len(self.intervals) and self.intervals[i][0] <= r+1:
            new_l = min(new_l, self.intervals[i][0])
            new_r = max(new_r, self.intervals[i][1])
            self.total -= self.intervals[i][1] - self.intervals[i][0] + 1
            remove.append(i)
            i += 1
        for j in reversed(remove):
            self.intervals.pop(j)
        self.intervals.insert(bisect_left(self.intervals, [new_l, new_r]), [new_l, new_r])
        self.total += new_r - new_l + 1
    def count(self) -> int:
        return self.total
1

// Not practical in Rust without BTreeMap or similar, see C++/Python/Java.

1

// Not practical in TypeScript without ordered map, see Python/Java/C++.

Complexity

  • ⏰ Time complexity: O(log n) per add/count operation, due to interval merging and binary search.
  • 🧺 Space complexity: O(n), for storing the intervals.