热乎狗家电面面经

一直觉得狗家电面就很难，前一阵子拼命的准备dp，图，结果砸在了intersection上，废话不多说了，上题

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

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

求米下锅！！祝大家好运。

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

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

用sweep line写了下，需要每次改process的timestamps

1. struct Proc {
   
2.     string name;
   
3.     int start;
   
4.     int end;
   
5.     Proc(string name, int start, int end) : name(name), start(start), end(end) { }
   
6.     bool operator< (const Proc& p) const
   
7.     {
   
8.         return start < p.start;
   
9.     }
   
10. };
    
11. 
    
12. vector<pair<string, int>> processExclusiveTime(vector<Proc>& procs)
    
13. {
    
14.     multiset<pair<int, string>> ps;
    
15.     unordered_map<string, int> runnings;
    
16.     unordered_map<string, int> res;
    
17.     for (auto& p : procs)
    
18.     {
    
19.         ps.insert({p.start, p.name});
    
20.         ps.insert({p.end, p.name});
    
21.     }
    
22.     // concurrent running count
    
23.     int cur = 0;
    
24.     for (auto& p : ps)
    
25.     {
    
26.         int t = p.first;
    
27.         string name = p.second;
    
28.         if (cur == 1)
    
29.         {
    
30.             auto it = runnings.begin();
    
31.             res[it->first] += t - it->second;
    
32.         }
    
33.         // start p process
    
34.         if (runnings.emplace(name, t).second)
    
35.             ++cur;
    
36.         else
    
37.         {
    
38.             --cur;
    
39.             runnings.erase(name);
    
40.         }
    
41.         // update all time stamps for running instance
    
42.         for (auto& pt : runnings)
    
43.             pt.second = t;
    
44.     }
    
45.     vector<pair<string, int>> runtimes;
    
46.     copy(res.begin(), res.end(), back_inserter(runtimes));
    
47.     return runtimes;
    
48. }

复制代码

LC636 ?         

wtcupup 发表于 2019-8-24 02:42
LC636 ?

不太一样，636是单线程，这个是多线程，但是要找同一时间段只有一个线程在工作的时间。

不太明白题目意思，每个元素包含开始结束时间，比如 proc {id1, 100, 200}, {id2, 150, 300} ... 所以 proc id1 [100,150] ? 所有先按起始时间sort一下

Line sweep?

baldmice 发表于 2019-8-24 03:47
不太明白题目意思，每个元素包含开始结束时间，比如 proc {id1, 100, 200}, {id2, 150, 300} ... 所以 proc ...

嗯，你这个例子就是返回 {id1, 50} {ID2, 100} 只算单独运行的时间

撸炉卤鹿 发表于 2019-8-24 04:05
Line sweep?

好像是，刚搜了一下这个名次，之前没练习过，惭愧

woridage1 发表于 2019-8-24 04:16
好像是，刚搜了一下这个名次，之前没练习过，惭愧

其实先sort一下，用stack也可以做。。。

面经看的少了　这个问题好像刚有人面过

撸炉卤鹿 发表于 2019-8-24 04:19
其实先sort一下，用stack也可以做。。。

hmmm, stack怎么做？先开始的可能比后面的进程先结束了