2276

2276. Count Integers in Intervals (Hard)

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.

Companies: Google, LinkedIn, Bloomberg

Related Topics:
Design, Segment Tree, Ordered Set

Similar Questions:

• Merge Intervals (Medium)
• Insert Interval (Medium)
• Data Stream as Disjoint Intervals (Hard)
• My Calendar III (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/count-integers-in-intervals
// Author: github.com/lzl124631x
// Time:
//      CountIntervals: O(1)
//      add: O(N) where N is the maximum number of intervals
//      count: O(1)
// Space: O(N)
class CountIntervals {
    int cnt = 0;
    map<int, int, greater<>> m; // left -> right
    int overlap(int a, int b, int c, int d) {
        if (a > c) swap(a, c), swap(b, d);
        return b - c + 1 - max(0, b - d);
    }
public:
    void add(int left, int right) {
        auto it = m.lower_bound(right); // find the greatest interval whose left boundary <= `right`.
        int d = right - left + 1, L = left, R = right;
        for (; it != m.end() && it->second >= left; it = m.erase(it)) {
            d -= overlap(it->first, it->second, left, right);
            L = min(L, it->first);
            R = max(R, it->second);
        }
        m[L] = R;
        cnt += d;
    }
    int count() {
        return cnt;
    }
};