253这题，为啥按照结束时间排序先

还有一题是56 merge interval的题是按照start time 排序


什么时候是按照start时间排，什么时候按照结束时间排，有点晕掉了。

大家能给个思路吗？  


253是end时间排序。

求大神指点

一般而言，如果题目可以转化为求minimum number of intervals that cover the whole range，推荐用sort by starting points;
如果题目可以转化为求maximum number of intervals that do not overlap，推荐用sort by ending points;

这题可以按start time排吧，起码我一直这么排的，然后在把end time 放到最小堆里

253是interval partition，如何用最少的处理器处理所有interval使各interval都不重叠，是贪心的经典题，按照start time遍历interval，每次把interval放进一个“闲置”容器，放入后容器的下一次闲置时间为该interval的end time，如果interval开始时没有闲置容器就要增加一个容器。而这题可贪心的点在于，每次只需要查找一个“最有可能”的闲置容器，而那个“最后可能”就是end time最早的interval所在的容器。
当然实现上你不需要真的创建这些容器，因为实际你只看一个容器对应的end time，所以把start time（象征interval）和end time（象征最有可能容器）分别排序，然后双指针遍历即可，如果当前S[ i] < E[j]，表示没有闲置容器，需要增加容器，否则就占据该容器，j++

1. def minMeetingRooms(intervals):
   
2.         starts = sorted(i.start for i in intervals)
   
3.         ends = sorted(i.end for i in intervals)
   
4.         i = cnt = 0
   
5.         for s in starts:
   
6.                 if s < ends: cnt += 1
   
7.                 else: i += 1
   
8.         return cnt

复制代码

另外还有一个贪心的经典例题是435，那是interval scheduling问题，是只给你一个处理器，问你最多能处理多少interval使各interval都不重叠，那题只需要按照end time排序，因为end time最早的interval“最有可能”容纳更多的其他interval

YouTube 上搜每日一题一个博主，最近他就是在讲解这个。这种是贪心范畴的。

这个就涉及贪心算法的证明了。

这个题的证明可以参考《Algorithm Design》第4章第1节，interval scheduling.

你可以这么考虑 假设room的个数为1 并且对于某一时刻t = t0 可以schedule的time intervals有{[s1, e1], [s2, e2], [s3, e3], ..., [sn, en]} (任意si >= t0) 此时你需要选择一个time interval去schedule 选择后将去掉所有与之conflict的time intervals (也即开始时间晚于这个time interval的结束时间) 你会怎么选
很明显 在当前这一步 选择结束时间最早的time interval可以最多地保留可被schedule的time intervals 那么当选好之后 就进入到下一时刻t = t1 (刚刚被选的time interval的结束时间) 并且做与刚刚相同的事情 这推出了为何贪心算法可以得到最优解

探究最少需要多少个room的时候 可以把问题转化成让每个room里schedule的time intervals尽可能多 那么思路就是跟room数为1时基本上相同 因此也是考虑根据end time来从小到大排序

meeting room或classroom放课，这典型的教科书题