Coding - My Calendar I

Problem Statement

Implement a MyCalendar class to store your events. A event is defined as a half-open interval [start, end), where start <= end.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half-open interval [start, end), meaning the event ends at end but does not include the end time itself.

Here are the specific rules for a valid booking:

1. [start, end) should be a valid interval.
2. [start, end) should not overlap with any interval that was created before, because double booking is not allowed.

When a call to book(start, end) returns true, it means the event can be booked, so no overlapping events exist. Otherwise, it returns false and the event cannot be booked.

Your MyCalendar class will be instantiated and called like so:

plaintext MyCalendar cal = new MyCalendar(); boolean canBook = cal.book(start, end);

Examples

Example 1:

plaintext MyCalendar(); MyCalendar.book(10, 15); // returns true MyCalendar.book(15, 20); // returns true MyCalendar.book(10, 20); // returns false

Explanation:

• The first event can be booked. (No overlapping events).
• The second event can be booked. (After the first event, no overlapping events).
• The third event CANNOT be booked. (It overlaps with the first event).

Example 2:

plaintext MyCalendar(); MyCalendar.book(1, 3); // returns true MyCalendar.book(2, 4); // returns false

Explanation:

• The first event can be booked. (No overlapping events).
• The second event CANNOT be booked. (It overlaps with the first event because the first event ends at time 3 and the second event starts at time 2).

Constraints

• The number of calls to MyCalendar.book method will be in the range [1, 1000].
• 0 <= start < end <= 10^9

Follow-up**

• Implement the MyCalendar class with O(n) query time complexity.
• Could you extend your solution to one where MyCalendar can handle overlapping booking requests? How would that change the new API?