LeetCode in Kotlin

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.

Solution

import java.util.TreeMap

@Suppress("NAME_SHADOWING")
class CountIntervals {
    private val map: TreeMap<Int, Int> = TreeMap()
    private var count: Int

    init {
        map[-1] = -1
        map[1000000001] = 1000000001
        count = 0
    }

    fun add(left: Int, right: Int) {
        var left = left
        var right = right
        var item = if (map.floorEntry(left).value < left) map.ceilingEntry(left) else map.floorEntry(left)
        while (item.key <= right) {
            left = Math.min(left, item.key)
            right = Math.max(right, item.value)
            count -= item.value - item.key + 1
            map.remove(item.key)
            item = map.ceilingEntry(item.key)
        }
        map[left] = right
        count += right - left + 1
    }

    fun count(): Int {
        return count
    }
}
/*
 * Your CountIntervals object will be instantiated and called as such:
 * var obj = CountIntervals()
 * obj.add(left,right)
 * var param_2 = obj.count()
 */

This site is open source. Improve this page.