题目
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 toadd
andcount
. - 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点赞!