My Calendar I
My Calendar I is a medium intervals problem solved with the basics pattern.
The best approach, optimal (ordered map of start → end), runs in O(log n) per booking time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every booking) up.
Problem
Build a booking calendar that never allows two events to overlap. Each event is a half-open time range [start, end): it covers every moment t with start <= t < end, so an event ending at 10 and another starting at 10 do not clash.
Implement the class MyCalendar:
MyCalendar()creates an empty calendar.boolean book(int start, int end)adds the event and returnstrueif it does not overlap any event already in the calendar. Otherwise the calendar is left unchanged and it returnsfalse.
Examples
Example 1
- Input
MyCalendar(), book(5, 12), book(10, 15), book(12, 20)- Output
true, false, true- Why
- [10, 15) overlaps [5, 12) at times 10 and 11; [12, 20) starts exactly when [5, 12) ends, so it fits.
Example 2
- Input
MyCalendar(), book(30, 40), book(0, 30), book(25, 35), book(40, 41)- Output
true, true, false, true- Why
- Touching end points are fine, but [25, 35) collides with both earlier bookings.
Constraints
0 <= start < end <= 10^9- At most
1000calls tobook.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (check every booking) | O(n) per booking | O(n) |
| Optimal (ordered map of start → end) | O(log n) per booking | O(n) |
1Brute force (check every booking)
O(n) per bookingEach call scans all n bookings accepted so far, O(n²) over all calls.O(n)One pair per accepted booking.Store accepted bookings in a list. For a new request, compare it with every stored booking using the overlap test; accept and store it only if nothing overlaps.
- For each stored
[s, e): ifstart < e && s < end, return false. - Otherwise append
[start, end)and return true.
class MyCalendar {
private final List<int[]> booked = new ArrayList<>();
public MyCalendar() {}
public boolean book(int start, int end) {
for (int[] b : booked) {
if (start < b[1] && b[0] < end) return false;
}
booked.add(new int[] { start, end });
return true;
}
}class MyCalendar:
def __init__(self):
self.booked = []
def book(self, start: int, end: int) -> bool:
for s, e in self.booked:
if start < e and s < end:
return False
self.booked.append((start, end))
return Trueclass MyCalendar {
vector<pair<int, int>> booked;
public:
MyCalendar() {}
bool book(int start, int end) {
for (auto& b : booked) {
if (start < b.second && b.first < end) return false;
}
booked.push_back({start, end});
return true;
}
};class MyCalendar {
constructor() {
this.booked = [];
}
book(start, end) {
for (const [s, e] of this.booked) {
if (start < e && s < end) return false;
}
this.booked.push([start, end]);
return true;
}
}2Optimal (ordered map of start → end)
O(log n) per bookingTwo tree lookups and one insertion, each O(log n) in a balanced tree (the sorted-list versions pay O(n) for the insert shift).O(n)One map entry per accepted booking.Keep accepted bookings in a map sorted by start. Since accepted bookings never overlap, the new interval can only clash with its two neighbours: the booking with the greatest start <= start (it must end by start) and the booking with the smallest start >= start (it must begin at or after end).
prev= floor entry ofstart; if it exists andprev.end > start, return false.next= ceiling entry ofstart; if it exists andnext.start < end, return false.- Insert
start → endand return true. - Python and JavaScript have no built-in tree map, so they keep a sorted list of starts and use binary search for the neighbours.
class MyCalendar {
private final TreeMap<Integer, Integer> cal = new TreeMap<>();
public MyCalendar() {}
public boolean book(int start, int end) {
Map.Entry<Integer, Integer> prev = cal.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
Map.Entry<Integer, Integer> next = cal.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
cal.put(start, end);
return true;
}
}class MyCalendar:
def __init__(self):
self.starts = []
self.ends = []
def book(self, start: int, end: int) -> bool:
i = bisect.bisect_right(self.starts, start)
if i > 0 and self.ends[i - 1] > start:
return False
if i < len(self.starts) and self.starts[i] < end:
return False
self.starts.insert(i, start)
self.ends.insert(i, end)
return Trueclass MyCalendar {
map<int, int> cal;
public:
MyCalendar() {}
bool book(int start, int end) {
auto next = cal.lower_bound(start);
if (next != cal.end() && next->first < end) return false;
if (next != cal.begin()) {
auto prev = std::prev(next);
if (prev->second > start) return false;
}
cal[start] = end;
return true;
}
};class MyCalendar {
constructor() {
this.starts = [];
this.ends = [];
}
book(start, end) {
let lo = 0, hi = this.starts.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.starts[mid] <= start) lo = mid + 1;
else hi = mid;
}
const i = lo;
if (i > 0 && this.ends[i - 1] > start) return false;
if (i < this.starts.length && this.starts[i] < end) return false;
this.starts.splice(i, 0, start);
this.ends.splice(i, 0, end);
return true;
}
}Edge cases to test
- A new booking that ends exactly where an existing one starts (allowed)
- A new booking that completely contains an existing one, or sits strictly inside one
- Rejected bookings must not be stored
- Bookings arriving in decreasing order of time
Hints
Hint 1
Two half-open intervals [s1, e1) and [s2, e2) overlap exactly when s1 < e2 and s2 < e1.
Hint 2
Checking every stored booking works, but only two stored bookings can matter: the one that starts just before the new start and the one that starts at or after it.
Hint 3
Keep the bookings ordered by start time (a balanced tree / sorted map) so both neighbours can be found in O(log n).
FAQ
What is the best time complexity for My Calendar I?
Optimal (ordered map of start → end) runs in O(log n) per booking time and O(n) extra space. Two tree lookups and one insertion, each O(log n) in a balanced tree (the sorted-list versions pay O(n) for the insert shift).
Which pattern does My Calendar I use?
It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.
Is there a brute force solution for My Calendar I?
Yes. Brute force (check every booking) takes O(n) per booking time and O(n) space. Store accepted bookings in a list.
Which edge cases should I test for My Calendar I?
A new booking that ends exactly where an existing one starts (allowed); A new booking that completely contains an existing one, or sits strictly inside one; Rejected bookings must not be stored; Bookings arriving in decreasing order of time.