狗家电面

谷歌电面：

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

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

请问楼主 执行中的进程是根据starting time已经排好序的吗

新的task只有一个的话就扫描一遍查找有没有conflict吧，只有这一道吗

楼主做完狗家OA后，多久被联系要安排面试的？

黎明之前 发表于 2019-10-23 10:36
新的task只有一个的话就扫描一遍查找有没有conflict吧，只有这一道吗

如果有多个query呢？先merge overlap的interval?还有啥更好的思路嘛？

C++ Solution 使用 upper_bound(二叉搜索)
class Solution {
public:
    bool isConflict(vector<pair<string, vector<int>>>&schedule, pair<string, vector<int>> newProgram) {
        map<int, int> scheduleMap; //Start-End time
        for (pair<string, vector<int>> oneSchedule : schedule)
                scheduleMap[oneSchedule.second[0]] = oneSchedule.second[0] + oneSchedule.second[1];
        int newStart = newProgram.second[0];
        int newEnd = newProgram.second[0] + newProgram.second[1];
        auto itStart = scheduleMap.upper_bound(newStart);
        auto itEnd = scheduleMap.upper_bound(newEnd);
        if (itStart == itEnd) {
            --itStart;
            if ((*itStart).second <= newStart) return false;
        }
        return false;
    }
};

betterztt 发表于 2019-10-27 12:23
如果有多个query呢？先merge overlap的interval?还有啥更好的思路嘛？

不是说了“进程之间不能有conflict”嘛

zjzijidlu 发表于 2019-10-23 09:56
请问楼主 执行中的进程是根据starting time已经排好序的吗

好像并不需要排序？

jayqiu16 发表于 2019-10-29 10:31
C++ Solution 使用 upper_bound(二叉搜索)
class Solution {
public:

if ((*itStart).second <= newStart) return false; 这应该是return true吧？