最近，我接受了一个采访。我被要求设计一个会议安排程序，就像在 Microsoft Outlook 日历或 gmail 日历中一样。我建议我每天创建一个 48 个数组。每 30 分钟代表一个数组条目。
我必须确保下一次约会不会与上一次会议发生冲突。
我的解决方案运行良好，但浪费了太多内存。
谁能告诉我如何找到更好的解决方案来检测会议碰撞。
我不知道一开始的所有会议。它们将在以后随机添加。
谢谢，
问问题
19054 次
5 回答
17
从一个空的会议列表开始，每个会议都有一个start_time和duration。我们将按 . 维护排序的会议列表start_time。
要将会议添加到列表中，请通过执行二分搜索找到它在列表中的所属位置。找到索引后，执行两次检查以避免冲突；考虑即将插入的会议之前和之后的会议（如果存在）。
- 断言前会议的
start_time + duration不超过新会议的start_time。 - 断言新会议的
start_time+duration不超过会后的start_time。
如果断言得到满足，则将会议添加到列表中。
此添加操作需要O(log(list_size))时间。
注意：此方法假定添加具有重叠的会议是无效操作。如果允许存在重叠，您将不得不在新会议之前/之后的会议之外进行检查。
于 2013-03-01T03:53:29.853 回答
7
We can have a Tree structure (BST) for storing the requests (Request object: start time/end time/date/priority etc.). By doing so, add/delete/search/update operations can be achieved by O(height_of_tree). If we use a balanced tree, we can get the optimized running time. i.e. O(log n) for each of the above mentioned operations.
This approach is better than the sorted list approach as the list is backed by an fixed sized array in case of ArrayList which takes O(n) for copying the elements from old array to new array. If we use a linkedlist, binary search is not possible.
Comments welcome!
于 2015-02-21T23:07:29.173 回答
3
这是我使用二进制搜索插入的解决方案
public class MeetingScheduler {
static class Meeting implements Comparable<Meeting> {
Date startTime;
Date endTime;
int duration;
public static final int MINUTE = 60000;
//duration in minutes
Meeting(Date startTime, int duration) {
this.startTime = startTime;
this.duration = duration;
this.endTime = new Date(startTime.getTime() + (MINUTE * duration));
}
@Override
public int compareTo(Meeting o) {
if (this.endTime.compareTo(o.startTime) < 0) {
return -1;
}//end time is before the other's start time
if (this.startTime.compareTo(o.endTime) > 0) {
return 1;
}////start time is after the other's end time
return 0;
}
@Override
public String toString() {
return "meeting {" +
"from " + startTime +
", minutes=" + duration +
'}';
}
}
private List<Meeting> meetings = new ArrayList<Meeting>();
public Meeting bookRoom(Meeting meeting) {
if (meetings.isEmpty()) {
meetings.add(meeting);
return null;
} else {
int pos = -Collections.binarySearch(meetings, meeting);
if (pos > 0) {
meetings.add(pos-1, meeting);
return null;
} else {
return meetings.get(-pos);
}
}
}
public List<Meeting> getMeetings() {
return meetings;
}
public static void main(String[] args) {
MeetingScheduler meetingScheduler = new MeetingScheduler();
Meeting[] meetingsToBook = new Meeting[]{
//October 3rd 2014
new Meeting(new Date(2014 - 1900, 10 - 1, 3, 15, 00), 15),
new Meeting(new Date(2014 - 1900, 10 - 1, 3, 16, 00), 15),
new Meeting(new Date(2014 - 1900, 10 - 1, 3, 17, 00), 60),
new Meeting(new Date(2014 - 1900, 10 - 1, 3, 18, 00), 15),
new Meeting(new Date(2014 - 1900, 10 - 1, 3, 14, 50), 10),
new Meeting(new Date(2014 - 1900, 10 - 1, 3, 14, 55), 10)
};
for (Meeting m : meetingsToBook) {
Meeting oldMeeting = meetingScheduler.bookRoom(m);
if (oldMeeting != null) {
System.out.println("Could not book room for " + m + " because it collides with " + oldMeeting);
}
}
System.out.println("meetings booked: " + meetingScheduler.getMeetings().size());
for (Meeting m : meetingScheduler.getMeetings()) {
System.out.println(m.startTime + "-> " + m.duration + " mins");
}
}
}
于 2014-12-18T04:36:00.560 回答
0
虽然使用排序数组和二分查找是有效的，但请注意插入将花费 o(n) 假设没有发现冲突，因为数组需要滑动会议。不确定这是否是最佳解决方案。
于 2014-01-09T08:32:14.937 回答
0
如果排序列表是一个数组，我相信添加操作将花费 O(n)，因为您必须转移在要插入的会议之后开始的会议。
于 2014-01-13T23:03:31.610 回答