facebook面经 interval problem

 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


Ans:

treat each start and end time as a point, sort the points,
now process each point in order,
if hit a start time, cnt ++
if hit an end time, cnt --

the max of cnt in the process is the number of meeting rooms needed.

there is one catch
这个解法有个注意事项，如果interval 1的start time 和interval 2 的end time相等
，应该把 interval 2的 end time排在前面

不然像（２，　３），(3, 4)这样的可能返回2，实际应该返回1.


The following is a wrong dp solution:
 按pair.first sort,
f[i]为从第0个到第i个时间段需要的最小房间数
那么if(pair[i].first>=pair[i-1].second) f[i]=f[i-1]
else f[i]=f[i-1]+1

counterexample:（1，3）（2，6），（4，5）
 the result of the algo is 3, but the correct answer is 2