Skip to content

Latest commit

 

History

History
90 lines (83 loc) · 4.12 KB

README.md

File metadata and controls

90 lines (83 loc) · 4.12 KB

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:

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;
    }
};