facebook 二面题目求解题思路

interval [startTime, stopTime)   ----integral  time stamps
给这样的一串区间 I1, I2......In  
找出 一个 time

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

6-3-13 03:47):
具体代码参照后面。meeting room 变形。

这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room，也就是某个时刻有几个并行的会议，这个题目求时刻有最大的并行interval数量，差不多，按照start time排一遍，再用一个heap放结束时间就可以了。贴个python版本的：

1. 
   
2. import heapq
   
3. def integraltimestamps2(intervals):
   
4.     intvs = sorted(intervals, key = lambda x : x[0])
   
5.     edges = sorted([intv[0] for intv in intervals]+[intv[1] for intv in intervals])
   
6.     results = []
   
7.     moccurs = 0
   
8.     ongoing = []
   
9.     intvid = 0
   
10.     for e in edges:
    
11.         if results and len(ongoing) == moccurs:
    
12.             results += range(results[-1]+1,e)
    
13.         while ongoing and e >= ongoing[0]:
    
14.             heapq.heappop(ongoing)
    
15.         while intvid < len(intvs) and e >= intvs[intvid][0]:
    
16.             heapq.heappush(ongoing, intvs[intvid][1])
    
17.             intvid += 1
    
18.         if len(ongoing) > moccurs:
    
19.             moccurs = len(ongoing)
    
20.             results = [e]
    
21.         elif len(ongoing) == moccurs:
    
22.             results.append(e)
    
23.     return results

复制代码

把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1，否则-1，算出最大的interval overlap数。接下来具体最多的overlap在哪里也很容易找吧

Java 版本的，感觉跟skyline很像， 最后没返回结果直接打印出来了

1. public static void FindMaxStamp(List<int[]> intervals){
   
2.                 List<int[]> ret = new ArrayList<>();
   
3.                 List<int[]> res = new ArrayList<>();
   
4.                 for(int[] interval : intervals){
   
5.                         System.out.println("input:" + interval[0] + "," + interval[1]);
   
6.                         res.add(new int[]{interval[0], 1});
   
7.                         res.add(new int[]{interval[1], -1});
   
8.                 }
   
9.                 Collections.sort(res, new Comparator<int[]>(){
   
10.                         public int compare(int[] a, int[] b){
    
11.                                 return a[0] - b[0];
    
12.                         }
    
13.                 });
    
14.                 int max = 0, num = 0, start = 0;
    
15.                 for(int[] pos : res){
    
16.                         if(pos[1] == 1){//start point
    
17.                                 num++;
    
18.                                 start = pos[0];
    
19.                         }else{// end point
    
20.                                 if(num == max){
    
21.                                         ret.add(new int[]{start, pos[0]});
    
22.                                 }else if(num > max){
    
23.                                         max = num;
    
24.                                         ret = new ArrayList<>();
    
25.                                         ret.add(new int[]{start, pos[0]});
    
26.                                 }
    
27.                                 num--;
    
28.                         }
    
29.                 }
    
30.                
    
31.                 for(int[] temp : ret){
    
32.                         System.out.println(":["+temp[0] + "," + temp[1] + ")");
    
33.                 }
    
34.         }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

又想了一個，merge interval 變形, merge的部分，也就是重疊的部分，用hashmap計數，最後返回map最高的，寫看看代碼，等會上

1. public class Solution {
   
2.     public static void main(String[] args) {
   
3.         List <Interval> list = new ArrayList<>();
   
4.         list.add(new Interval(1,3));
   
5.         list.add(new Interval(2,7));
   
6.         list.add(new Interval(4,8));
   
7.         list.add(new Interval(5,9));
   
8.         List<Integer> result = findMost(list);
   
9.         for (Integer it : result) {
   
10.             System.out.println(it);
    
11.         }
    
12.     }
    
13. 
    
14.     public static List<Integer> findMost(List <Interval> intervals) {
    
15.         //assume intervals sorted
    
16.         List<Integer> result = new ArrayList<>();
    
17.         if (intervals == null || intervals.size() == 0)
    
18.             return result;
    
19. 
    
20.         Map<Integer, Integer> map = new HashMap<>();
    
21.         List <Interval> newIntervals = new ArrayList<>();//merged list
    
22.         newIntervals.add(intervals.get(0));
    
23.         for (int i = 1; i < intervals.size(); i++) {
    
24.             Interval pre = newIntervals.get(newIntervals.size() -1);
    
25.             Interval cur = intervals.get(i);
    
26.             int s = -1, e = -1;//overlap interval
    
27.             if (cur.start < pre.end) {
    
28.                 s = cur.start;
    
29.             } else {
    
30.                 newIntervals.add(cur);
    
31.                 continue;
    
32.             }
    
33.             if (cur.end <= pre.end) {
    
34.                 e = cur.end;
    
35.             } else {
    
36.                 e = pre.end;
    
37.                 pre.end = cur.end;
    
38.             }
    
39.             for (int j = s; j < e; j++) {
    
40.                 if (map.containsKey(j)) {
    
41.                     map.put(j, map.get(j)+1);
    
42.                 } else {
    
43.                     map.put(j, 2);
    
44.                 }
    
45.             }
    
46.         }
    
47. 
    
48.         if (map.size() == 0) {
    
49.             // if no over lap
    
50.             for (Interval in : intervals) {
    
51.                 for (int i = in.start; i < in.end; i++) {
    
52.                     result.add(i);
    
53.                 }
    
54.             }
    
55.             return result;
    
56.         } else {
    
57.             int max = 0;
    
58.             for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    
59.                 if (entry.getValue() > max) {
    
60.                     max = entry.getValue();
    
61.                     result.clear();
    
62.                     result.add(entry.getKey());
    
63.                 } else if (entry.getValue() == max) {
    
64.                     result.add(entry.getKey());
    
65.                 }
    
66.             }
    
67.         }
    
68.         return result;
    
69.     }
    
70. }
    
71. 
    
72. class Interval{
    
73.     //[ start, end )
    
74.     int start;
    
75.     int end;
    
76. 
    
77.     public Interval(int start, int end) {
    
78.         this.start = start;
    
79.         this.end = end;
    
80.     }
    
81. }

复制代码

补充内容 (2016-3-12 10:25):
HashMap的空間還能進一步減少，使用TreeMap, 每次有重疊的interval時，取出小於重疊部分之前的數據并計算最大值，這樣能保證總interval很長的時候map不會太大

xutopia 发表于 2016-3-12 10:22
把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1，否则-1，算出最大的interval overlap ...

可以再清楚點嘛？

xutopia 发表于 2016-3-12 10:22
把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1，否则-1，算出最大的interval overlap ...

牛啊，DP的思想。这一遍过的时候就可以不断更新最大的overlap数，同时更新区间。

另一个思路，如果nlogn 可以用binary index tree.  interval update single query。timestamp 需要离散化，细节得注意。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

xutopia 发表于 2016-3-12 10:22
把所有的startTime和stopTime排序过一遍。碰到start当前interval数+1，否则-1，算出最大的interval overlap ...

大神能指导的详细一点儿么？