731. My Calendar II

UnknownView on LeetCode

Array Binary Search Design Segment Tree Ordered Set

Time: O(n²)

Space: O(n)

Intuition

Allow double booking but not triple. Track single and double bookings as sorted interval lists.

Algorithm

1Maintain list of double-booked and single-booked intervals.
2On book(s,e): check if new interval overlaps with any double-booked interval → reject.
3Add overlaps of new interval with single-booked intervals to double-booked.
4Add new interval to single-booked.

Common Pitfalls

•Order matters: check double first. Overlap = max(s1,s2) < min(e1,e2).

731.cs

// Approach: Sweep line with a difference map (+1 at start, -1 at end); reject booking if running prefix sum would exceed 2.
// Time: O(n²) Space: O(n)

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

    public bool Book(int start, int end)
    {
        timeline[start] = timeline.GetValueOrDefault(start, 0) + 1;
        timeline[end] = timeline.GetValueOrDefault(end, 0) - 1;

        int activeEvents = 0;

        foreach (var count in timeline.Values)
        {
            activeEvents += count;
            if (activeEvents > 2)
            {
                timeline[start] = timeline.GetValueOrDefault(start, 0) - 1;
                if (timeline[start] == 0)
                    timeline.Remove(start);

                timeline[end] = timeline.GetValueOrDefault(end, 0) + 1;
                if (timeline[end] == 0)
                    timeline.Remove(end);

                return false;
            }
        }

        return true;
    }
}

Was this solution helpful?