Google 一道VO高频题的解答讨论

最近看面经发现一道VO高频题：task scheduler。想和大家讨论一下解法。题目是说一堆task和M个CPU看

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

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

k K*M*logN
感觉时间复杂度不是很优秀，求问有没有大神有更好的解法。

calendar III 的变体。顺手贴一下 lee215大神的 答案

单个CPU 内的task 应该本来就是sorted 的， sort M 个CPU 复杂度是 N*logM 。 遍历sorted array 找到所有overlapped intervals 以及每个interval 下工作CPU的数量, O(n).    每次插入遍历overlapped intervals, 如果与 overlapped number < M 则可以插入。

如果只是回答可不可以，那么如果任意一点的最大overlap个数<=M，就可以插入。反之不行。所以复杂度O(NlogN)，如果已经排好序O(N)。

不是lc calendar 那题得升级版吗

难道不是calendar III 那道题题一模一样吗

tw_arthur 发表于 2021-1-22 10:59
calendar III 的变体。顺手贴一下 lee215大神的 答案

这题用sweep line不是更简单吗？

1. class MyCalendarThree {
   
2. public:
   
3.     multiset<pair<int,int>>Set;
   
4.    
   
5.     MyCalendarThree()
   
6.     {
   
7.         
   
8.     }
   
9.    
   
10.     int book(int start, int end)
    
11.     {
    
12.         Set.insert({start,1});
    
13.         Set.insert({end,-1});
    
14.         
    
15.         int count=0;
    
16.         int result=0;
    
17.         for (auto a: Set)
    
18.         {
    
19.             count+=a.second;
    
20.             result = max(result,count);
    
21.         }
    
22.         return result;
    
23.         
    
24.     }
    
25. };
    
26. 
    
27. /**
    
28. * Your MyCalendarThree object will be instantiated and called as such:
    
29. * MyCalendarThree obj = new MyCalendarThree();
    
30. * int param_1 = obj.book(start,end);
    
31. */

复制代码