Amazon Interview-Design Meeting Scheduler

Ответ 1

Начните с пустого списка встреч, каждый с start_time и duration. Мы будем вести отсортированный список встреч start_time.

Чтобы добавить собрание в список, найдите, где он принадлежит в списке, выполнив двоичный поиск. Когда вы найдете индекс, выполните две проверки, чтобы избежать столкновения; рассмотрите собрания непосредственно перед и после собрания, которое будет вставлено (если они существуют).

• Утверждение перед встречей start_time + duration не превышает новое собрание start_time.
• Утверждение нового собрания start_time+duration не превышает послепродажное start_time.

Если утверждения выполнены, добавьте собрание в список.

Эта операция добавления занимает время O(log(list_size)).

Примечание. Этот подход предполагает, что добавление встречи с перекрытием является недопустимой операцией. Если перекрытия разрешены к существованию, вам придется проверить за пределами встреч, непосредственно предшествующих/после нового собрания.

Ответ 2

Мы можем иметь структуру дерева (BST) для хранения запросов (объект запроса: время начала/время окончания/дата/приоритет и т.д.). Таким образом, операции добавления/удаления/поиска/обновления могут быть достигнуты с помощью O (height_of_tree). Если мы используем сбалансированное дерево, мы можем получить оптимизированное время работы. то есть O (log n) для каждой из вышеупомянутых операций.

Этот подход лучше, чем метод отсортированного списка, поскольку список поддерживается массивом фиксированного размера в случае ArrayList, который принимает O (n) для копирования элементов из старого массива в новый массив. Если мы используем связанный список, двоичный поиск невозможен.

Комментарии приветствуются!

Ответ 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 start time
            if (this.startTime.compareTo(o.endTime) > 0) {
                return 1;
            }////start time is after the other 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");
        }

    }
}

Ответ 4

в то время как использование сортированного массива и двоичного поиска является эффективным, обратите внимание, что вставка будет принимать o (n), если не будет найдено столкновение, так как массиву необходимо скопировать собрания. Не уверен, что это наиболее оптимальное решение.

Ответ 5

Если отсортированный список является массивом, я полагаю, что операция добавления будет принимать O (n), так как вы должны перенести встречу, которая начинается после встречи с вставкой.