LC 253 Meeting Rooms II 易解说的思路

传送门

这题的讨论已经很成熟了，我个人最喜欢的解法是这个
原本的解相当简短，排序完后一个for-loop秒解
但是里头的if-condition真的是太难解释了
面试时要是不能好好的解释给面试官听
就算解出来了，面试官还是得把你给挂了

所以我稍微改了一下原解法，会比较好解释，简单说明一下：
stack记录当前所需的meeting room数
res记录stack的最高值

底下的for-loop可以想像成，把所有的start跟end依照时间排序, 每遇到start就得多开一个房间(stack++), 每遇到end就可以把一个房间给关了(stack--)
如此一来, 在for-loop遍历所有的event之下, res可以记录下所需最多房间的数量。

注意，如果时间一样，end会比start优先(ex: stack: 4 -> 3 -> 4)，这样才不会多开了一个房间(ex: stack: 4 -> 5 -> 4)，这概念跟skyline有点相像
这也是为什么我用了if (starts[i] < ends[j])而不是if (starts[i] <= ends[j])

1. class Solution {
   
2.     public int minMeetingRooms(Interval[] intervals) {
   
3.         int n = intervals.length;
   
4.         int[] starts = new int[n];
   
5.         int[] ends = new int[n];
   
6.         for(int i = 0; i < n; i++) {
   
7.             starts[i] = intervals[i].start;
   
8.             ends[i] = intervals[i].end;
   
9.         }
   
10.         Arrays.sort(starts);
    
11.         Arrays.sort(ends);
    
12.         int stack = 0;
    
13.         int res = 0;
    
14.         for(int i = 0, j = 0; i < n;) {
    
15.             if (starts[i] < ends[j]) {
    
16.                 stack++;
    
17.                 res = Math.max(res, stack);
    
18.                 i++;
    
19.             } else {
    
20.                 stack--;
    
21.                 j++;
    
22.             }
    
23.         }
    
24.         return res;
    
25.     }
    
26. }

复制代码

其实把一个开会的区间想象成一对匹配的括号，然后根据时间排列这些左右括号之后，会议室的数量就是括号的最大深度了，这样更好理解。

这个问题比较早在D. R. Ford , D. R. Fulkerson, Flows in Networks这本书里提到过（两个作者名字合起来就是Ford-Fulkerson.. 最大流算法）：
https://www.rand.org/content/dam/rand/pubs/reports/2007/R375.pdf

第120页，证明过程是作为Dilworth定理的一个推论：

Minimal number of individuals to meet a fixed schedule of tasks ... It follows from Dilworth's theorem that the fewest number of individuals required is equal to the maximal number of tasks, no two of which can be performed by the same individual.

关于Dilworth定理的描述和证明，参考这份notes:
http://math.mit.edu/~cb_lee/18.318/lecture8.pdf

简单来说，要理解Meeting Room II的正确性，最关键的是要证明“求最少房间数”这一原问题与“寻找最大重叠区间”这一对偶问题的等价性

证明过程大概就是先定义一个偏序关系：定义区间A < B，当且仅当A、B不相交且A的时间在B之前

然后根据此偏序关系由上面那份notes里的内容定义链（chain）和反链（anti-chain），这里chain映射到两两互不冲突的区间集合，anti-chain则映射到两两全都冲突的区间集合。

现在问题转化成了要将区间集合划分成若干个chain，我们希望最小化chain的数量（因为每个chain对应一个房间）。

而根据Dilworth定理，chain的最小数量等于anti-chain的最大容量，所以我们转而求原问题的对偶问题（duality）—— anti-chain最大容量。

根据定义可知一个anti-chain中的所有区间必须两两相交，再根据cantor's intersection theorem可知anti-chain中的所有区间必然同时相交于至少一点。所以问题转化为寻找所有时间点上重叠的最大区间数，也就是用台阶（staircase）算法，等同于主贴中描述的：

每遇到start就得多开一个房间(stack++), 每遇到end就可以把一个房间给关了(stack--)

赞一个...
楼主的改进的做法跟我的一样，利口Discussion里面那个对于starts和ends的处理感觉并不好解释...

觉得这题真是相当绕，几个答案虽然结果是对的但是不太想得通为什么这样是对的，或者说如何证明？

哈哈。写的很清楚。感谢分享！！！！

这题用start，end双数组排序还是比较容易理解的
我不明白https://blog.csdn.net/qq508618087/article/details/50762939里面第二种解法

1. /**
   
2. * Definition for an interval.
   
3. * struct Interval {
   
4. *     int start;
   
5. *     int end;
   
6. *     Interval() : start(0), end(0) {}
   
7. *     Interval(int s, int e) : start(s), end(e) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     int minMeetingRooms(vector<Interval>& intervals) {
    
13.         map<int, int> hash;
    
14.         for(auto val: intervals)
    
15.             hash[val.start]++, hash[val.end]--;
    
16.         int ans = 0, sum = 0;
    
17.         for(auto val: hash)
    
18.             sum += val.second, ans = max(ans, sum);
    
19.         return ans;
    
20.     }
    
21. };

复制代码

这是正确的吗？我跑了一下程序，完全不对啊

补充内容 (2019-2-11 11:00):
我好久没用c++了，也许c++这样在map中插入key，value pair是会顺序排列的，但大部分语言map插入值后是乱序的

步惊云 发表于 2019-2-11 09:24
回头看了一眼, 其实你问这个就是我想说的答案.

我第四种方法里面如果长度很大的话, 就得用map做, 跟sk ...

https://blog.csdn.net/yy254117440/article/details/53889594

我现在明白了，要用有序map来做，一般语言中map是无序的，要特殊处理一下

1. /**
   
2. * Definition of Interval:
   
3. * classs Interval {
   
4. *     int start, end;
   
5. *     Interval(int start, int end) {
   
6. *         this->start = start;
   
7. *         this->end = end;
   
8. *     }
   
9. * }
   
10. */
    
11. 
    
12. class Solution {
    
13. public:
    
14.     /**
    
15.      * @param intervals: an array of meeting time intervals
    
16.      * @return: the minimum number of conference rooms required
    
17.      */
    
18.     int minMeetingRooms(vector<Interval> &intervals) {
    
19.         // Write your code here
    
20.         
    
21.         if (intervals.empty()) {
    
22.             return 0;
    
23.         }
    
24.         
    
25.         std::sort(intervals.begin(), intervals.end(),
    
26.                 [](const Interval &s1, const Interval &s2) -> bool {
    
27.             return s1.start < s2.start;
    
28.         });
    
29.         
    
30.         int size = intervals.size();
    
31.         
    
32.         int last_end = 0;
    
33.         
    
34.         vector<bool> marks(size, false);
    
35. 
    
36.         std::queue<int> q;
    
37.         q.push(0);
    
38.         
    
39.         int cnt = 0;
    
40.         
    
41.         while (!q.empty()) {
    
42.             
    
43.             int j = q.front();
    
44.             q.pop();
    
45.             
    
46.             last_end = intervals[j].end;
    
47.             
    
48.             if (marks[j]) {
    
49.                 continue;
    
50.             } else {
    
51.                 marks[j] = true;
    
52.             }
    
53.             
    
54.             cnt++;
    
55.             
    
56.             for (j = j + 1; j < size; j++) {
    
57.                
    
58.                 if (marks[j]) {
    
59.                     continue;
    
60.                 }
    
61.                
    
62.                 if (last_end > intervals[j].start) {
    
63.                     q.push(j);
    
64.                 } else {
    
65.                     marks[j] = true;
    
66.                     last_end = intervals[j].end;
    
67.                 }
    
68.             }
    
69.             
    
70.         }
    
71.         
    
72.         return cnt;
    
73.     }
    
74. };

复制代码

请问这段代码有可能通过面试吗？纯粹模拟运行
因为 starts/ends sort + 一趟遍历求出答案的方法真的不明白