亚马逊面试-设计会议安排程序

Question

最近，我参加了一次面试。被要求设计一个会议安排程序，就像Microsoft Outlook日历或Gmail日历中的那样。

我建议为每天创建一个包含48个元素的数组，每30分钟表示一个数组条目。

我必须确保下一个约会不会与之前的会议发生冲突。

我的解决方案运行良好，但浪费了太多内存。

请问有人能告诉我如何找到更好的解决方案以检测会议的冲突？

我不知道所有会议的情况。它们将在之后随机添加。

谢谢。

- yuvi

---

它没有包括重复的日程安排吗？比如每个工作日早上09:00 - 15分钟的Scrum。每个星期五16:00 - 团队在食堂聚会喝茶？ - जलजनक

他们要求我完全独立设计。没有提供任何输入。 - yuvi

我们如何为多天维护会议安排程序？所以，假设我创建了一个长度为48天的数组，但这只是为一天创建的吗？如果我想安排第二天的会议，我该怎么保存呢？ - mshikher

Answer 1

开始时，我们需要一个空的会议列表，每个会议都有开始时间和持续时间。我们将通过“开始时间”来维护一个会议排序列表。

要向列表中添加会议，请执行二进制搜索以找到它在列表中的位置。一旦找到索引，执行两个检查以避免冲突；考虑刚好在待插入会议之前和之后的会议（如果存在）。

1. 断言前一个会议的 "开始时间 + 持续时间" 不超过新会议的 "开始时间"。 2. 断言新会议的 "开始时间+持续时间" 不超过后一个会议的 "开始时间"。

如果满足这些断言，则将会议添加到列表中。

此添加操作需要O(log(list_size)) 的时间。

注意：此方法假定具有重叠的会议是无效操作。 如果允许存在重叠，则必须检查新会议之前/之后的会议之外的会议。

- cheeken

---

我想我忘了提到这件事。一开始我没有权限访问所有的会议。 - yuvi

在已排序的列表中添加元素需要O（列表大小）的时间。我有什么遗漏吗？ - damned

@damned 使用二分查找，可以在O(log(list_size))的时间内执行添加操作。请参阅：http://en.wikipedia.org/wiki/Binary_search_tree#Insertion - cheeken

你是使用二叉搜索树还是列表？在二叉搜索树中查找前驱和后继可能会导致O（树的高度）的时间复杂度，这可能是O（n）。 - damned

如果我需要检查一个时间点是否可用，我认为问题中建议的方法比这个方法更快。我错了吗？此外，这种方法相对于问题中建议的方法有哪些优势？ - Kaushik Sivakumar

Answer 2

我们可以采用树形结构（二叉搜索树）来存储请求（请求对象：开始时间/结束时间/日期/优先级等）。这样，添加/删除/搜索/更新操作的时间复杂度为O (树的高度)。如果使用平衡树，则可以获得优化的运行时间，即上述每个操作的时间复杂度为O(log n)。

与有序列表方法相比，该方法更好，因为列表是由固定大小的数组支持的，对于ArrayList，从旧数组复制元素到新数组需要O(n)的时间复杂度。如果使用链表，则无法进行二分查找。

欢迎评论！

- Vinoth

---

有一个问题。为了保持BST中的结构，应该采取什么方法...我尝试使用KD树方法...其中奇数级别（根级别为1）将根据开始时间排序，偶数级别将根据结束时间排序。 - FatherMathew

Answer 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");
        }

    }
}

- CCC

Answer 4

如果排序列表是一个数组，我相信添加操作将需要O(n)的时间，因为您必须移动在待插入会议之后开始的会议。

- Kelvin

Answer 5

虽然使用排序数组和二分查找是高效的，但请注意，如果没有发现冲突，插入将需要o(n)的时间，因为数组需要滑动会议。不确定这是否是最优解决方案。

- Kelvin