最近、インタビューを受けました。Microsoft Outlook カレンダーや Gmail カレンダーと同じように、ミーティング スケジューラの設計を依頼されました。私は、毎日 48 個の配列を作成することを提案しました。配列エントリを表す 30 分ごと。
次の予定が前の会議と重ならないようにする必要があります。
私のソリューションは正常に機能しますが、メモリを浪費しすぎます。
会議の衝突を検出するためのより良い解決策を見つける方法を教えてください。
最初はすべての会議を知っているわけではありません。後でランダムに追加されます。
ありがとう、
空の会議リストから始めます。各リストにはとが付いていstart_timeますduration。でソートされた会議のリストを維持しstart_timeます。
会議をリストに追加するには、バイナリ検索を実行して、会議がリスト内のどこに属しているかを見つけます。インデックスを見つけたら、衝突を避けるために2つのチェックを実行します。挿入される会議の直前と直後の会議を検討します（存在する場合）。
start_time + duration、新しいミーティングのを超えないようにしstart_timeます。start_time+durationをアフターミーティングのを超えないように主張しstart_timeます。アサーションが満たされている場合は、会議をリストに追加します。
この追加操作にはO(log(list_size))時間がかかります。
注：このアプローチでは、重複する会議を追加することは無効な操作であると想定しています。重複が許可されている場合は、新しい会議の直前/直後の会議を超えて確認する必要があります。
リクエストを格納するためのツリー構造 ( BST ) を持つことができます (リクエスト オブジェクト: 開始時刻/終了時刻/日付/優先度など)。そうすることで、O(height_of_tree)で追加/削除/検索/更新操作を実現できます。バランスの取れたツリーを使用すると、最適化された実行時間を得ることができます。つまり、上記の操作のそれぞれについてO(log n)です。
古い配列から新しい配列に要素をコピーするために O(n) を取る ArrayList の場合、リストは固定サイズの配列によってサポートされるため、このアプローチはソートされたリストのアプローチよりも優れています。リンクリストを使用すると、二分探索はできません。
コメント大歓迎！
これが、バイナリ検索を使用して挿入する私のソリューションです
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");
}
}
}
ソートされた配列と二分探索の使用は効率的ですが、配列は会議をスライドさせる必要があるため、競合が見つからないと仮定すると、挿入は o(n) を取ることに注意してください。これが最適なソリューションかどうかはわかりません。