920.會(huì)議室
描述
給定一系列的會(huì)議時(shí)間間隔，包括起始和結(jié)束時(shí)間[[s1,e1]，[s2,e2]，…(si < ei)，確定一個(gè)人是否可以參加所有會(huì)議。
Example
樣例1
輸入: intervals = [(0,30),(5,10),(15,20)]
輸出: false
解釋:
(0,30), (5,10) 和 (0,30),(15,20) 這兩對(duì)會(huì)議會(huì)沖突
樣例2
輸入: intervals = [(5,8),(9,15)]
輸出: true
解釋:
這兩個(gè)時(shí)間段不會(huì)沖突
class Solution:
? ? def canAttendMeetings(self, intervals):
? ? ? ? intervals.sort(key = lambda x: x.start)
? ? ? ? for i in range(1,len(intervals)):
? ? ? ? ? ? if intervals[i].start < intervals[i-1].end:
? ? ? ? ? ? ? ? return False
? ? ? ? return True
思路就是排序之后再比較是否有重疊區(qū)間。
919.會(huì)議室 2
給定一系列的會(huì)議時(shí)間間隔intervals，包括起始和結(jié)束時(shí)間[[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的會(huì)議室數(shù)量。
Example
樣例1
輸入: intervals = [(0,30),(5,10),(15,20)]
輸出: 2
解釋:
需要兩個(gè)會(huì)議室
會(huì)議室1:(0,30)
會(huì)議室2:(5,10),(15,20)
樣例2
輸入: intervals = [(2,7)]
輸出: 1
解釋:
只需要1個(gè)會(huì)議室就夠了
這道題運(yùn)用了掃描線的思路，將起始時(shí)間和結(jié)束時(shí)間在x軸上標(biāo)記，然后計(jì)數(shù)，遇到起始時(shí)間就+1（打開一個(gè)會(huì)議室），遇到結(jié)束時(shí)間就-1（關(guān)閉一個(gè)會(huì)議室），取這個(gè)過程中的最大值，則是需要的最小會(huì)議室數(shù)。
"""
Definition of Interval.
class Interval(object):
? ? def __init__(self, start, end):
? ? ? ? self.start = start
? ? ? ? self.end = end
"""
class Solution:
? ? def minMeetingRooms(self, intervals):
? ? ? ? # Write your code here
? ? ? ? start = []
? ? ? ? end = []
? ? ? ? for i in intervals:
? ? ? ? ? ? start.append(i.start)
? ? ? ? ? ? end.append(i.end)
? ? ? ? start.sort()
? ? ? ? end.sort()
? ? ? ? a , b = 0 , 0
? ? ? ? min_room = 0
? ? ? ? count_room = 0
? ? ? ? while a < len(start):
? ? ? ? ? ? if start[a] < end[b]:
? ? ? ? ? ? ? ? count_room += 1
? ? ? ? ? ? ? ? a += 1
? ? ? ? ? ? ? ? min_room = max(min_room , count_room)
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? count_room -= 1
? ? ? ? ? ? ? ? b += 1
? ? ? ? return min_room
