题目

https://leetcode.com/problems/count-integers-in-intervals/

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.

思路

题目大意是事实插入区间，求区间内的总数。

维护一个有序的区间数组，每次插入时候二分查找定位位置，插入/合并新区间，同时更新下整数个数即可。

在hard题目里算是非常水的了。

代码

二分查找注意边界条件；合并区间时处理好终止条件和计数即可。

class CountIntervals(object):

    def __init__(self):
        self.intervals = []
        self.cnt = 0

    def add(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: None
        """
        l, r = 0, len(self.intervals)
        while l < r:
            mid = l + (r - l) // 2
            # 第一个i.right >= left的区间
            if self.intervals[mid][1] < left:
                l = mid + 1
            else:
                r = mid
        if l >= len(self.intervals):
            self.intervals.append((left, right))
            self.cnt += right - left + 1
        else:
            i = l
            while i < len(self.intervals) and self.intervals[i][0] <= right and self.intervals[i][1] >= left:
                interval2 = self.intervals.pop(i)
                self.cnt -= interval2[1] - interval2[0] + 1
                left, right = min(left, interval2[0]), max(right, interval2[1])
            self.intervals.insert(i, (left, right))
            self.cnt += right - left + 1

    def count(self):
        """
        :rtype: int
        """
        return self.cnt

比较少见的lc一次过，收工！

——此处是内容的分割线——

除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接

本文链接：https://www.utopiafar.com/2022/07/07/leetcode-2276-count-integers-in-intervals/

码字不易，如果觉得内容有帮助，欢迎留言or点赞！