脸熟体验不是很好的电面

lorii 发表于 2021-02-19 23:54:47
非常感谢这个帖子和这个回复！ 面到了类似的变种题 用的二分的思路做了 今天通知过了 希望楼主和层主都好运！

恭喜！ 能帮到地里的各位就好

多谢分享

follow up,  一个list比另一个短特别多的情况:  O(MlogN)，M是短list的长度，N是长list的长度

1. class Solution {
   
2. public:
   
3.     vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
   
4.         int n_first = firstList.size();
   
5.         int n_second = secondList.size();
   
6.             
   
7.         if (n_first < n_second) {
   
8.             for (auto &interval : firstList)
   
9.                 binary_search(interval, secondList);
   
10.         } else {
    
11.             for (auto &interval : secondList)
    
12.                 binary_search(interval, firstList);
    
13.         }   
    
14.             
    
15.         return result;
    
16.     }   
    
17.         
    
18. private:
    
19.     vector<vector<int>> result;
    
20. 
    
21.     void binary_search(vector<int> &interval, vector<vector<int>> &longList) {
    
22.         auto comp = [](const vector<int> &interval1, const vector<int> &interval2) {
    
23.             return interval1[1] < interval2[1];
    
24.         };  
    
25.             
    
26.         vector<int> itv = {interval[0], interval[0]};
    
27.         auto it_left = lower_bound(longList.begin(), longList.end(), itv, comp);
    
28.         if (it_left == longList.end())
    
29.             return;
    
30.             
    
31.         itv = {interval[1], interval[1]};
    
32.         auto it_right = lower_bound(longList.begin(), longList.end(), itv, comp);
    
33.         if (it_right != longList.end())
    
34.             it_right++;
    
35.       
    
36.         for (; it_left < it_right; it_left++) {
    
37.             vector<int> overlap = {max(interval[0], (*it_left)[0]),
    
38.                              min(interval[1], (*it_left)[1])};
    
39.                
    
40.             if (overlap[0] <= overlap[1])
    
41.                 result.push_back(overlap);
    
42.         }   
    
43.     }   
    
44. };

复制代码