下午刚刚面的。电话迟到了5/6min, 上来就说,我们先来做题,之后有时间再聊。题目不是特别难,但是没给任何输入输出什么的。然后写testcase还写了好久。。。这块真是个坑。。。开始题意理解了一下,然后讨论了一下时间复杂度啊,input什么的之类的
最后写到四点,面试官说,会议室有人来了,我再给你5min, 毕竟我迟到了,我说好,他就把电话挂了,之后我以为他会在链接里说几句什么的,结果 都!没! 有!
我自己测好了,还在那问,也没消息。然后我也不知道怎么办了。。。chat里面聊也没回。。。自己在那无聊又改了下tc测也没问题了。。。后来他也没在线了。。。我就自己关了。。。
真是我经历过最神奇的面试了。。。总有wrap up一下什么的吧。。。感觉面试官压根没在意我再说什么在写什么,好像很匆忙的样子。。。如果大家需要,我可以把我的代码贴上来。。。但写的有点屎。。。
题目我直接贴上来好了
// Find all available time periods to hold a meeting for a set of attendees, given the following:
// 1. Schedules of all attendees (when they are busy)
// 2. A time range to hold the meeting
// 3. Meeting duration
// Example:
// Inputs:
// Busy Schedule for person p1 : [1,4), [7,11), [15,19)
// Busy Schedule for person p2 : [4,6), [8,9), [11,13), [20,29)
// Busy Schedule for person p3 : [4,10), [25,35)
// Time range to hold the meeting: [0, 100]
// Meeting Duration: 1
// Output:
// All available time periods to hold the meeting: [[0, 1), [13, 15), [19, 20), [35, 100]]
merge intervals LC 吾刘有一部分吧。。。还有一部分是亿两两久
贴一个我当时写的代码吧
class Scheduler{
List<List<List<Integer>>> schedule;
List<Integer> duration;
int timeRange;
public Scheduler(List<List<List<Integer>>> schedule, List<Integer> duration, int timeRange){
this.schedule = schedule;
this.duration = duration;
this.timeRange = timeRange;
}
public List<List<Integer>> schedule(){
if (duration == null || duration.size() != 2 || duration.get(1) - duration.get(0) + 1 < timeRange || timeRange <= 0) return null;
List<List<Integer>> ans = new ArrayList<>();
List<List<Integer>> merged = merge();
int start = duration.get(0);
int end = duration.get(1);
for (List<Integer> list : merged){
if (list.get(0) > end) break;
int curEnd = list.get(0);
if (curEnd - start + 1 >= timeRange){
List<Integer> interval = new ArrayList<>();
interval.add(start);
interval.add(curEnd);
ans.add(interval);
}
start = Math.max(start, list.get(1));
}
if (end - start + 1 >= timeRange) {
List<Integer> interval = new ArrayList<>();
interval.add(start);
interval.add(end);
ans.add(interval);
}
return ans;
}
public List<List<Integer>> merge(){
List<List<Integer>> ans = new ArrayList<>();
if (schedule == null || schedule.size() == 0) return ans;
List<List<Integer>> prev = schedule.get(0);
for (int i = 1; i < schedule.size(); i++){
List<List<Integer>> next = new ArrayList<>();
List<List<Integer>> cur = schedule.get(i);
int ind1 = 0, ind2 = 0;
while (ind1 < prev.size() && ind2 < cur.size()){
if (prev.get(ind1).get(0) > cur.get(ind2).get(1)){
next.add(cur.get(ind2));
ind2++;
} else if (cur.get(ind2).get(0) > prev.get(ind1).get(1)){
next.add(prev.get(ind1));
ind1++;
} else {
int start = Math.min(cur.get(ind2).get(0), prev.get(ind1).get(0));
int end = Math.max(cur.get(ind2).get(1), prev.get(ind1).get(1));
if (cur.get(ind2).get(1) > prev.get(ind1).get(1)){
cur.get(ind2).set(0, start);
cur.get(ind2).set(1, end);
ind1++;
} else {
prev.get(ind1).set(0, start);
prev.get(ind1).set(1, end);
ind2++;
}
}
}
if (ind1 == prev.size()){
while (ind2 < cur.size()){
next.add(cur.get(ind2++));
}
} else if (ind2 == cur.size()){
while (ind1 < prev.size()){
next.add(prev.get(ind1++));
}
}
prev = next;
}
return prev;
}