DDSA Solutions

729. My Calendar I

MediumView on LeetCode
ArrayBinary SearchDesignOrdered SetSegment Tree
Time: O(n log n)
Space: O(n)

Problem Overview

Maintain a sorted list of booked intervals.

Intuition

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

Algorithm

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

Common Pitfalls

  • •Check both floor (booking that starts before) and ceiling (booking that starts after) for overlaps.
729.cs
C#
// 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?

Related Problems