狗狗太阳谷跪经

foryousee 发表于 2018-11-8 09:48
多谢，感觉是应该可以n解出来的，因为记得有一个定理记得是可以用任意点做一条线平分所有点

还能记得起是什么定理啊？是不是还要保证任意三点不能再同一条直线上？我画了半天感觉应该是这样

1. public List<List<int[]>> setMeetingRooms(int[][] intervals) {
   
2.         List<List<int[]>> res = new ArrayList<>();
   
3.         Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
   
4.         for (int i = 0; i < intervals.length; i++) {
   
5.             int[] interval = intervals[i];
   
6. 
   
7.             boolean set = false;
   
8.             for (List<int[]> list : res) {
   
9.                 if (list.get(list.size() - 1)[1] <= interval[0]) {
   
10.                     list.add(interval);
    
11.                     set = true;
    
12.                 }
    
13.             }
    
14.             if (!set) {
    
15.                 List<int[]> newList = new ArrayList<>();
    
16.                 newList.add(interval);
    
17.                 res.add(newList);
    
18.             }
    
19.         }
    
20.         return res;
    
21.     }
    

复制代码

请问下楼主，第一题是这个思路么？

wawavint 发表于 2018-11-8 12:10
还能记得起是什么定理啊？是不是还要保证任意三点不能再同一条直线上？我画了半天感觉应该是这样

我面的时候小姐姐有说保证没有三线共点保证是偶数个点。楼主这个题不知道有没有这些条件，如果没有就要复杂很多，可能不存在解

KenZhuJMHK 发表于 2018-11-8 12:20
我面的时候小姐姐有说保证没有三线共点保证是偶数个点。楼主这个题不知道有没有这些条件，如果没有就要复 ...

enen。谢谢啦，如果有的话确实难度增加不少

第二题怎么做的·？贪心算法么？

pastpast 发表于 2018-11-8 12:30
第二题怎么做的·？贪心算法么？

dfs + memorization (cache)可解的。利口有原题，具体的我忘记了，你可以搜一下～

wawavint 发表于 2018/11/08 12:10:13


还能记得起是什么定理啊？是不是还要保证任意三点不能再同一条直线上？我画了半天感觉应该是这样

很初级的一个定理，名字实在记不起来了。有三点共线就找下一个点画。直到找到一个点就行了。点在向量的左右有很多应用。比如顺时针的polygon，一个点在所有向量的右侧就会在polygon内

foryousee 发表于 2018-11-7 22:02
如果是level越低interval越多，就先生成结果，然后排序，越少的放越低的level

请问这里 "越少" 指的是什么呀? 没搞懂题意..

bc2615 发表于 2018-11-9 10:16
请问这里 "越少" 指的是什么呀? 没搞懂题意..

指的是level。就是最后返回结果是一个list的list<interval>，list 0里面应该是有最多interval的list<Interval>

wtcupup 发表于 2018-11-8 09:35
最后一轮用 一个k size 的 BST maintain sorted data， 用一个queue maintain最近的k， when queue size bi ...

请问5%这个条件是怎么处理的啊？