Facebook Additional Phone Interview

感觉把start time和end time拆开来，排个序就好了吧。。start time权值为1，end time权值-1

1guangnian 发表于 2014-11-18 09:02
感觉把start time和end time拆开来，排个序就好了吧。。start time权值为1，end time权值-1

This is my final answer...but lz did not finish....crycrycry

为什么lz的实习面都这么难。。。其他全职的onsite都很多原题的感觉。。。

论坛匿名用户 发表于 2014-11-18 09:04
This is my final answer...but lz did not finish....crycrycry

pat pat...

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

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

pazzaintermilan 发表于 2014-11-18 09:07
为什么lz的实习面都这么难。。。其他全职的onsite都很多原题的感觉。。。

fate               

不用急， intern 的 bar并不高。

北美农民 发表于 2014-11-18 10:25
不用急， intern 的 bar并不高。

请烧纸                  

求问大神，如何用segement tree做，插入的时候当某个区间往下递归的时候跨了几个区间，怎么标记以及查询的时候怎么回收统计的值？或者别的思路？？

先排序，然后再扫一遍，感觉代码写的很冗余。

1. 
   
2. struct CompareStart
   
3. {
   
4.     bool operator() (const Employee &a, const Employee &b){
   
5.         return a.startTime < b.startTime;
   
6.     }
   
7. };
   
8. 
   
9. struct CompareEnd
   
10. {
    
11.     bool operator() (const Employee &a, const Employee &b){
    
12.         return a.endTime < b.endTime;
    
13.     }
    
14. };
    
15. 
    
16. void PrintEmployeeWorkTime(vector<Employee> start_staff){
    
17.     int num_em = start_staff.size();
    
18.     if (num_em == 0) return;
    
19.     vector<Employee> end_staff(start_staff);
    
20.     sort(start_staff.begin(), start_staff.end(), CompareStart());
    
21.     sort(end_staff.begin(), end_staff.end(), CompareEnd());
    
22.     int idx_st = 1, idx_end = 0, count = 1, timestamp = start_staff[0].startTime;
    
23.     int cur_st, cur_end;
    
24.     while (start_staff[0].startTime == start_staff[idx_st].startTime) {idx_st++;count++;}
    
25. 
    
26.     while (idx_st < num_em || idx_end < num_em){
    
27.         cur_st = start_staff[idx_st].startTime;
    
28.         cur_end = end_staff[idx_end].endTime;
    
29.         cout << timestamp << "-" << min(cur_st,cur_end) << ":\t" << count << endl;
    
30.         if (cur_st <= cur_end){
    
31.             count++;
    
32.             idx_st++;
    
33.             while (idx_st < num_em && cur_st == start_staff[idx_st].startTime) {idx_st++;count++;}
    
34.             timestamp = cur_st;
    
35.         }
    
36.         if (cur_st >= cur_end){
    
37.             count--;
    
38.             idx_end++;
    
39.             while (idx_end < num_em && cur_end == end_staff[idx_end].endTime) {idx_end++;count--;}
    
40.             timestamp = cur_end;
    
41.         }
    
42.     }
    
43. }
    

复制代码