221. Diary Bookings
Design a small appointment diary for a busy doctor. A booking occupies the half-open time range [start, end): it includes minute start but not minute end, so one booking may begin at the exact minute another one finishes.
Implement the class Diary:
Diary()creates an empty diary.boolean book(int start, int end)tries to add a booking[start, end). If it does not overlap any booking already in the diary, record it and returntrue. If it overlaps even one existing booking by a single minute, change nothing and returnfalse.
A rejected request is never stored. The diary can receive up to 10,000 requests, so scanning every stored booking on each call is wasteful: keep the bookings in sorted order and find the neighbours of a new request quickly.
Example 1
- Input:
- operations = ["Diary","book","book","book"]arguments = [[],[10,20],[15,25],[20,30]]
- Output:
- [null,true,false,true]
- Explanation:
Outputs: [null, true, false, true]. [10,20) is free. [15,25) overlaps it, so it is rejected. [20,30) starts exactly when [10,20) ends, so it is allowed.
Example 2
- Input:
- operations = ["Diary","book","book","book","book","book"]arguments = [[],[5,8],[1,5],[0,100],[8,9],[3,4]]
- Output:
- [null,true,true,false,true,false]
- Explanation:
Outputs: [null, true, true, false, true, false]. [0,100) would swallow both stored bookings, and [3,4) lies inside [1,5).
Constraints
0 ≤ start < end ≤ 109
At most 104 calls to book
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log n) search per call
- Space
- O(n)