求这道面经题的解法

给你一堆Events，每个Event有start time和end time。Events的时间可能overlap。计算一个人当天最多可以参加几个events。

这道题貌似与以下interval相关的题目类似：
给定一堆interval，问最多的不相交的interval的个数是多少。

对于interval的问题，基本方法就是两个：排序然后使用贪心算法。
贪心算法的策略是：排序后，两个相交的interval移除EndTime大的那个。

回到楼主题目，我建议的思路是：排序，使用贪心算按天统计不相交的interval（Event）的数量。

补充内容 (2019-6-10 22:02):
时间复杂度：整体排序O(NLogN)，计算不相交的Interval数需要进行一次O(N)遍历。
因而整体时间复杂度是O(NLogN)

背包题目, 经典greedy题目.
按结束时间排序即可

感觉greedy似乎不行。给个反例：
Events = [1, 10], [2, 15], [11, 50], [12, 13], [13, 14]
这样Greedy排出来是这么三排不overlap的时间：
[1, 10], [11, 50]
[2, 15],
[12, 13], [13, 14]
即最多是2。但下面这种选法是3:
[1, 10], [12, 13], [13, 14]

贪心法。按结束时间排序。思想是：结束时间早的区间，因为对后续的影响最小，所以我们会优先收录。
所以，我们肯定会收录第一个区间后，接着顺次考察后续的区间，只要与第一个区间重叠的都会舍弃不看，直至找到下一个与第一个区间没有重叠的区间。这是最早结束的、与第一个区间无重叠的区间，因此是最优的，收录其中。
然后重复以上的步骤，直至考察完所有的区间。

wisdompeak2 发表于 2019-6-11 09:22
贪心法。按结束时间排序。思想是：结束时间早的区间，因为对后续的影响最小，所以我们会优先收录。
所以， ...

感觉这个方法讲得通。但还是没有说服自己为什么这么做一定是对的。即有没有可能在某一步选择最先结束的时候并不是最优的方案？不知道怎么证明这个是不可能的。

参考楼上说的方法，写了一个代码。暂时没有找到反例：

1. import java.util.*;
   
2. 
   
3. public class Solution {
   
4.   public static void main(String[] args) {
   
5.     Event[] events = new Event[] {
   
6.       new Event(1, 5),
   
7.       new Event(1, 4),
   
8.       new Event(2, 3),
   
9.       new Event(3, 4),
   
10.       new Event(4, 5),
    
11.     };
    
12.     List<Event> res = (new MyCode()).getMaxEvents(events);
    
13.     System.out.println(res.size());
    
14.     for(Event ev : res) {
    
15.       ev.print();
    
16.     }
    
17.   }
    
18. }
    
19. 
    
20. class MyCode {
    
21.   public List<Event> getMaxEvents(Event[] events) {
    
22.     List<Event> res = new LinkedList<>();
    
23.     if (events.length == 0) {
    
24.       return res;
    
25.     }
    
26.     Arrays.sort(events, (e1, e2) -> e1.e - e2.e); // 按照结束时间从小到大排序
    
27.     res.add(events[0]);
    
28.     int lastEnd = events[0].e;
    
29.     for (int i = 1; i < events.length; i++) {
    
30.       Event curr = events[i];
    
31.       if (curr.s >= lastEnd) {
    
32.         res.add(curr);
    
33.         lastEnd = curr.e;
    
34.       }
    
35.     }
    
36.     return res;
    
37.   }
    
38. }
    
39. 
    
40. class Event {
    
41.   int s;
    
42.   int e;
    
43.   public Event(int s, int e) {
    
44.     this.s = s;
    
45.     this.e = e;
    
46.   }
    
47.   public void print() {
    
48.     System.out.print("[" + this.s + ", " + this.e + "] ");
    
49.   }
    
50. }

复制代码

user123456 发表于 2019-6-11 17:20
感觉这个方法讲得通。但还是没有说服自己为什么这么做一定是对的。即有没有可能在某一步选择最先结束的时 ...

你不选择最先结束的区间的话，难道会选择晚结束的区间，去占用未来宝贵的时间资源吗？

wisdompeak2 发表于 2019/06/11 17:31:21


你不选择最先结束的区间的话，难道会选择晚结束的区间，去占用未来宝贵的时间资源吗？

Hmm...这个似乎是在用假设证明基于这个假设的结论

user123456 发表于 2019/06/11 08:34:47
感觉greedy似乎不行。给个反例：
Events = [1, 10], [2, 15], [11, 50], [12, 13], [13, 14]
这样Greedy排出来是这么三排不overla...

按结束时间sort