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

概述[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] 一文搞定合并区间及定会议室问题所遇到的程序开发问题。

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