[Python] 一文搞定合并区间及定会议室问题

[Python] 一文搞定合并区间及定会议室问题,第1张

概述[Python]一文搞定合并区间及定会议室问题相关leetcode题目56Mergeintervals合并区间252Meetingrooms会议室435Non-overlappingintervals非重叠区间253MeetingroomsII会议室2Reference相关leetcode题目56mergeintervals252Meetingrooms253Meetin

[Python] 一文搞定合并区间及定会议室问题相关leetcode题目56 Merge intervals 合并区间252 Meeting rooms 会议室435 Non-overlapping intervals 非重叠区间253 Meeting rooms II 会议室2Reference

相关leetcode题目

56 merge intervals

252 Meeting rooms

253 Meeting rooms II

435 Non-overlapping Intervals

56 Merge intervals 合并区间

题目重述:把有overlap的intervals进行合并,输出结果

基本解决思路:

首先,对原有的intervals进行排序。Python的排序方法使用lambda x:x[0]进行。遍历排序后的intervals。如果当前interval和之前的interval有overlap,进行合并;如果没有,把这个interval加入output

代码实现

class Solution:    def merge(self, intervals: List[List[int]]) -> List[List[int]]:        out = []        for i in sorted(intervals, key=lambda i: i[0]):            # 如果当前interval和之前的interval有overlap,进行合并            if out and i[0] <= out[-1][1]:                out[-1][1] = max(out[-1][1], i[1])            else:                out.append(i)        return out
252 Meeting rooms 会议室

同理可得。判断条件从 <= 变至 <. 上一个会议室结束时间和下一个会议室开始时间重合,并没有冲突。

class Solution:    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:        temp = []        for i in sorted(intervals, key=lambda x: x[0]):            if temp and i[0] < temp[-1][1]:                return 0            else:                temp.append(i)        return 1
435 Non-overlapPing intervals 非重叠区间

题目重述:找到不overlap的interval

注意点:如果[1,3]和[1,2]overlap,这边应该剔除哪一个呢?

这边个人觉得是[1,3]应该被提出。interval如果遇见conflict,越小越好,因为这样才能避免之后冲突的interval更多。举一个例子[1, 10000] 和 [1,2], [2,3] conflict, 这边肯定提出前者,因为他涵盖的范围太大而。所以在冲突判断的for循环里,从一开始的模板max改成min

class Solution:    def eraSEOverlAPIntervals(self, intervals: List[List[int]]) -> int:        count = 0        out = []        for i in sorted(intervals, key=lambda i: i[0]):            if out and i[0] < out[-1][1]:                # 把这边的max改成min                out[-1][1] = min(out[-1][1], i[1])                # 有重合,剔除                count += 1            else:                out.append(i)        return count
253 Meeting rooms II 会议室2

这道题暂时我没有想到用原模板解题的思路。

这边的解决方案和现实生活非常相似~上班的你想要找一个会议室开会,怎么办呢!你先去检查一下有没有空的房间,有的话(available-=1),如果没有,就要开一个新的 会议室(numRooms -=1)。你开完会了,会议室就空啦(available+=1)

对每一个会议的开始、结束时间进行排序用start,end双指针进行available和numRoom的更新
class Solution:    def minMeetingRooms(self, intervals: List[List[int]]) -> int:        starts = sorted([s[0] for s in intervals])        ends = sorted([s[1] for s in intervals])        s = e = 0        numRooms = available = 0        while s < len(starts):            if starts[s] < ends[e]:                if available == 0:                    numRooms += 1                else:                    available -= 1                s += 1            else:                available += 1                e += 1        return numRooms
Reference

https://leetcode.com/problems/merge-intervals/discuss/21227/7-lines-easy-Python
https://leetcode.com/problems/meeting-rooms-ii/discuss/67860/My-Python-Solution-With-Explanation

总结

以上是内存溢出为你收集整理的[Python] 一文搞定合并区间及定会议室问题全部内容,希望文章能够帮你解决[Python] 一文搞定合并区间及定会议室问题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1188533.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-03
下一篇 2022-06-03

发表评论

登录后才能评论

评论列表(0条)

保存