1/6 谷歌 电面

ecclesiastic 发表于 2016-3-4 13:54
这是leetcode 几乎是原题 meeting rooms II，就把原来的做法里算房间改成加时间就行，最优的是 O（n）

那个题我暂时只看到有O(n lg n)的解法https://leetcode.com/discuss/que ... g-rooms-ii?sort=hot，O(n)解法的思路是？

老印真没有黑你。这个题其实是bucket做

firemanysome 发表于 2016-3-4 14:11
老印真没有黑你。这个题其实是bucket做

请明示？字数字数字数字数

googlerr 发表于 2016-3-4 14:07
那个题我暂时只看到有O(n lg n)的解法https://leetcode.com/discuss/questions/oj/meeting-rooms-ii?sort ...

不好意思我想这个解法想错了，没算sort的时间：
https://leetcode.com/discuss/718 ... ution-beats-98-8%25

请楼主提供函数signature

楼主能加我qq吗？ QQ：1050237243

firemanysome 发表于 2016-3-4 23:50
请楼主提供函数signature

纯粹自己写。没有signature

这题我看到过貌似。
做法是先对ending time排序，这步是O(nlogn)，然后从小往大贪心的找下一个最近的ending time(beginning time > 上一个ending time)，这步是O(n)。
没想出来更快的做法。

wanyisjtu 发表于 2016-3-5 00:34
这题我看到过貌似。
做法是先对ending time排序，这步是O(nlogn)，然后从小往大贪心的找下一个最近的endin ...

仍然是O(n lg n)，我猜想对方应该不是要这种优化。

googlerr 发表于 2016-3-5 00:37
仍然是O(n lg n)，我猜想对方应该不是要这种优化。

那非要优化到O(n)只能纯哈希了，但是space就不知道有多大了。