Facebook电面

月亮有心 发表于 2016-10-18 04:10
我觉得是，因为全是数字的话数组大小不好控制

LC上那题是字母，所以怎么扫都是常数时间。楼主能详细讲下怎么维护heap吗？就是如果下一个可以安排的task不是heap里频率最高的那个？怎么从heap里取出来和维护呢？如果有代码就更好啦！

iPhD 发表于 2016-10-18 04:23
LC上那题是字母，所以怎么扫都是常数时间。楼主能详细讲下怎么维护heap吗？就是如果下一个可以安排的task ...

怎么会不是频率最高的那个呢，heap就是按频率大小来排的，下一个可以安排的task肯定就是heap顶部的那个，如果cooldown时间不够，就hold住，等时间够了再执行。

月亮有心 发表于 2016-10-18 04:32
怎么会不是频率最高的那个呢，heap就是按频率大小来排的，下一个可以安排的task肯定就是heap顶部的那个， ...

多谢，我问的是follow-up那个可以reorder，那样子第一个选出频率最高的，第二次如果要选出频率第二高的，这个怎么选？

iPhD 发表于 2016-10-18 04:40
多谢，我问的是follow-up那个可以reorder，那样子第一个选出频率最高的，第二次如果要选出频率第二高的， ...

为什么第二次要选出频率第二高的？第一问用不到heap的，然后reorder的目的是优化时间，并没有要求一定要先执行哪个

月亮有心 发表于 2016-10-18 04:43
为什么第二次要选出频率第二高的？第一问用不到heap的，然后reorder的目的是优化时间，并没有要求一定要 ...

不是有cooldown吗？比如cool down = 3, 如果task 1频率为10，task 2频率为5，那样子第一次选出task 1后，第二次因为cool down的原因，不能再选task 1了，得选频率第二高的task 2了？但在heap里最大的还是task 1

iPhD 发表于 2016-10-18 04:49
不是有cooldown吗？比如cool down = 3, 如果task 1频率为10，task 2频率为5，那样子第一次选出task 1后， ...

去看lc358的discussion， 那个题目你理解了，这个你也能做了。

iPhD 发表于 2016-10-18 04:49
不是有cooldown吗？比如cool down = 3, 如果task 1频率为10，task 2频率为5，那样子第一次选出task 1后， ...

看来你没懂这个heap是怎么操作的。。。你还是听楼上的去看discussion吧

iPhD 发表于 2016-10-18 04:49
不是有cooldown吗？比如cool down = 3, 如果task 1频率为10，task 2频率为5，那样子第一次选出task 1后， ...

如果照你的说法，1212121212，出现了5个1和5个2之后怎么办？不是还得连续的5个一么，跟一开始放5个1也没区别吧

但是感觉单纯用heap还是不行，毕竟比如12233这种cooldown是3的话，选完23之后要选1，需要保证在相同frequency的数字之间选一个离左边最远的，这个在lc358那里是个invalid的情况，但在这里还是要考虑，写了一下代码，欢迎指正

int arrangeTask(vector<int>& tasks, int cooldown) {
        unordered_map<int, int> count;
        for (auto task : tasks) {
                count[task]++;
        }
        unordered_map<int, int> lastPos;
        for (auto ele : count) {
                lastPos[ele.first] = -1;
        }
        auto comp = [&lastPos](pair<int, int> p1, pair<int, int> p2) {
                if (p1.first != p2.first) {
                        return p1.first < p2.first;
                }
                else {
                        return lastPos[p1.second] > lastPos[p2.second];
                }
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> queue(comp);
        for (auto ele : count) {
                queue.emplace(ele.second, ele.first);
        }
        int currPos = 0;
        while (!queue.empty()) {
                auto ele = queue.top();
                int fre = ele.first, num = ele.second;
                queue.pop();
                if (lastPos[num] != -1 && currPos - lastPos[num] - 1 < cooldown) {
                        currPos += cooldown - (currPos - lastPos[num] - 1);
                }
                lastPos[num] = currPos++;
                if (--fre > 0) {
                        queue.emplace(fre, num);
                }
        }
        return currPos;
}

经典面经题