Count Integers in Intervals LeetCode Solution

Problem – Count Integers in Intervals LeetCode Solution

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.

Count Integers in Intervals LeetCode Solution in C++

class CountIntervals {
public:
    map<int, int> m;
    int cnt = 0;
    void add(int left, int right) {
        auto it = m.upper_bound(left);
        if (it != begin(m) && prev(it)->second >= left)
            it = prev(it);
        for (; it != end(m) && it->first <= right; m.erase(it++)) {
            left = min(left, it->first);
            right = max(right, it->second);
            cnt -= it->second - it->first + 1;
        }
        cnt += right - left + 1;
        m[left] = right;
    }
    int count() { return cnt; }
};

Count Integers in Intervals LeetCode Solution in Java

class CountIntervals {
    TreeMap<Integer, Integer> m = new TreeMap<>();
    int cnt = 0;
    public void add(int left, int right) {
        var it = m.floorEntry(left);
        if (it == null || it.getValue() < left)
            it = m.higherEntry(left);
        for (; it != null && it.getKey() <= right; it = m.higherEntry(left)) {
            left = Math.min(left, it.getKey());
            right = Math.max(right, it.getValue());
            cnt -= it.getValue() - it.getKey() + 1;
            m.remove(it.getKey());
        }
        m.put(left, right);
        cnt += right - left + 1;        
    }
    public int count() { return cnt; }
}

Count Integers in Intervals LeetCode Solution in Python

from sortedcontainers import SortedList

class CountIntervals:

    def __init__(self):
        self.cnt = 0 
        self.intervals = SortedList()

    def add(self, left: int, right: int) -> None:
        k = self.intervals.bisect_left((left, right))
        while k < len(self.intervals) and self.intervals[k][0] <= right: 
            l, r = self.intervals.pop(k)
            self.cnt -= r - l + 1
            right = max(right, r)
        if k and left <= self.intervals[k-1][1]: 
            l, r = self.intervals.pop(k-1)
            self.cnt -= r - l + 1
            left = l
            right = max(right, r)
        self.cnt += right - left + 1
        self.intervals.add((left, right))

    def count(self) -> int:
        return self.cnt
Count Integers in Intervals LeetCode Solution Review:

In our experience, we suggest you solve this Count Integers in Intervals LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Find the Count Integers in Intervals LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Find the Count Integers in Intervals LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.