2017/7/13-Facebook电面

jingshihao 发表于 2017-7-28 09:19
发一个我想的跟大家交流下，基本思路就是排序之后一遍pass，如果当前busy interval 的开始是在 desired 的s ...

I think your solution assumes the given time ranges are already sorted and merged.

The interview seems to be interested to do merge and output generation in one pass.

Sort and no need to keep an array of merged busy ranges, only need to store the last busy range.
Do merge and outptu generation in one pass:

1. vector<TimeRange> availableRanges(TimeRange& desired, vector<TimeRange>& busy) {
   
2.         busy.emplace_back(desired.end, desired.end); // add dummy end
   
3.         sort(busy.begin(), busy.end(), [](TimeRange a, TimeRange b) { return a.start < b.start; });
   
4. 
   
5.         vector<TimeRange> available;
   
6.         TimeRange lastBusy(desired.start, desired.start); // dummy last busy range
   
7. 
   
8.         for (auto& b : busy) {
   
9.                 if (lastBusy.end >= desired.end) break;
   
10.                 if (b.start > lastBusy.end) {
    
11.                         available.emplace_back(lastBusy.end, min(b.start, desired.end));
    
12.                         if (b.start < desired.end) lastBusy = b;
    
13.                         else break;
    
14.                 }
    
15.                 else lastBusy.end = max(lastBusy.end, b.end);
    
16.         }
    
17.         return available;
    
18. }
    

复制代码

shuoshuo 发表于 2017-7-26 12:51
是不是可定义一个长度为24的boolean数组，busyt ime置为1， 找到meeting time的区间内为0的字段

The TimeRange class should be very generic with double type "start" and "end", so integer counting technique won't work.

bustu 发表于 2017-7-25 10:37
求问楼主，会议没有时长限制 是指什么呢？desired_time.start 和 desired_time.end 代表的是会议开始和结束 ...

The problem actually asks for remaining interval range [desired.start, desired.end] subtracted all busy ranges. The remaining intervals' lengths do not matter, all need to be collected as final result.

zzgzzm 发表于 2017-7-28 12:39
The problem actually asks for remaining interval range [desired.start, desired.end] subtracted all ...

Got it! thanks

Lyd. 发表于 2017-7-28 06:35
就是会议不需要一定持续多久。start和end只是一个区间，这个区间内任何非busy的时间段都可以排会议。

明白了，谢谢

楼主是今年5月毕业的，还是去年毕业的？

难道真的是 一题nohire 两题hire……

cgxy1991 发表于 2017-7-30 01:00
楼主是今年5月毕业的，还是去年毕业的？

17年5月毕业的

vtiaocao 发表于 2018-2-22 00:31
难道真的是 一题nohire 两题hire……

哈哈有这个说法吗？那我感到安慰了许多