729. My Calendar I

MediumView on LeetCode

Array Binary Search Design Ordered Set Segment Tree

Time: O(n log n)

Space: O(n)

Intuition

Maintain a sorted list of booked intervals. On book(s,e), check for overlap with neighbors.

Algorithm

1Use TreeMap with start→end entries.
2Find floorKey(start) → check if that booking's end > start (overlap).
3Find ceilingKey(start) → check if that booking's start < end (overlap).
4If no overlap, insert.

Common Pitfalls

•Check both floor (booking that starts before) and ceiling (booking that starts after) for overlaps.

729.cs

// Approach: SortedDictionary stores [start, end) pairs; find the predecessor and successor of the new interval and reject if they overlap.
// Time: O(n log n) Space: O(n)

public class MyCalendar
{
    private SortedDictionary<int, int> timeline = new SortedDictionary<int, int>();

    public bool Book(int start, int end)
    {
        if (timeline.Count == 0)
        {
            timeline.Add(start, end);
            return true;
        }

        var low = timeline.Keys.LastOrDefault(k => k < end);

        if (low == 0 && !timeline.ContainsKey(low) || timeline[low] <= start)
        {
            timeline.Add(start, end);
            return true;
        }

        return false;
    }
}

Was this solution helpful?