Meeting room
ref: http://www.fgdsb.com/2015/01/30/meeting-rooms/
Given a array of pairs where each pair contains the start and end time of a meeting (as in int),
Determine if a single person can attend all the meetings
For example:
Input array{ pair(1,4), pair(4, 5), pair(3,4), pair(2,3) }
Output: falseFollow up:
determine the minimum number of meeting rooms needed to hold all the meetings.
Input array{ pair(1, 4), pair(2,3), pair(3,4), pair(4,5) }
Output: 2
Follow up题也可以换一种形式：
Giving lots of intervals [ai, bi], find a point intersect with the most number of intervals
和Insert/Merge Intervals也属于一类题。
按start排序，找overlap
follow up:
#1 把所有interval的开始和结束点提取出来，vector<int> 里进行排序
#2 遇到开始 + 1，结束 - 1
类似于按时间轴进行扫描，在某一个时间点覆盖最多的interval的数量，为最大的需要房间数量
Read full article from Leetcode: Notes: from others
No comments:
Post a Comment