#729 My Calendar I

frequently reported atUber Intuit ByteDance / TikTok Google Amazon Oracle

the problem

In plain words

Implement MyCalendar.book(startTime, endTime) for half-open intervals [start, end). Add the event and return true unless it overlaps an existing one, in which case return false.

in book(10,20), book(15,25), book(20,30)

out true, false, true

[20,30) only touches [10,20) — touching is fine.

0 ≤ start < end ≤ 10⁹
At most 1000 calls to book

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternOrdered map / set (floor & ceiling)

Keep events sorted by start. A new event can only collide with its two neighbours: the last event starting before it (floor) and the first starting at or after it (ceiling).

solutions

From brute force to optimal

Compare the new interval with every stored one.

Overlap iff start < e.end && e.start < end.
No overlap → add.

timeO(n) per book

Scans every event → O(n²) over n calls.

spaceO(n)

All events.

javaclass MyCalendar (list)java.util.*

1class MyCalendar {2    private final List<int[]> events = new ArrayList<>();   // [start, end) pairs3 4    public boolean book(int startTime, int endTime) {5        for (int[] e : events) {6            // two half-open intervals overlap iff each starts before the other ends7            if (startTime < e[1] && e[0] < endTime) return false;8        }9        events.add(new int[] {startTime, endTime});10        return true;11    }12}

Check only the floor and ceiling neighbours.

before = floorEntry(start): conflict if before.end > start.
after = ceilingEntry(start): conflict if after.start < end.
Otherwise put(start, end).

timeO(log n) per book

Two lookups and one insert in a red-black tree.

spaceO(n)

One entry per booked event.

javaclass MyCalendar (TreeMap)java.util.*

1class MyCalendar {2    private final TreeMap<Integer, Integer> booked = new TreeMap<>();   // start → end, sorted by start3 4    public boolean book(int startTime, int endTime) {5        Map.Entry<Integer, Integer> before = booked.floorEntry(startTime);   // last event starting <= startTime6        if (before != null && before.getValue() > startTime) return false;   // it hasn't ended yet7        Map.Entry<Integer, Integer> after = booked.ceilingEntry(startTime);  // first event starting >= startTime8        if (after != null && after.getKey() < endTime) return false;        // it starts before we end9        booked.put(startTime, endTime);10        return true;11    }12}

in the room

How to say it in the interview

talk track

Write the overlap condition first: s1 < e2 && s2 < e1 for half-open intervals.
Explain why only two neighbours can conflict: stored events never overlap each other.

traps

Using <= in the overlap test — touching intervals [10,20) and [20,30) don't overlap.

what they ask next

Follow-ups

My Calendar II (LC 731) — allow double booking but not triple?

Keep a list of overlaps; or use a TreeMap difference array (+1 at start, −1 at end) and sweep — O(n) per booking.

before you submit

Edge cases to test

Touching bookings [10, 20) and [20, 30) → no overlap.
Same start as an existing booking → always a clash.
A new booking that covers an existing one completely → caught by ceilingEntry.

practise next