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

2021-11-22 17:26:50

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

相关leetcode题目
56 Merge intervals 合并区间
252 Meeting rooms 会议室
435 Non-overlapping intervals 非重叠区间
253 Meeting rooms II 会议室2
- Reference

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

码农公寓