290. My Calendar I

Maintain a sorted list of booked intervals. For each new booking, binary search to find where it would be inserted and check if it overlaps with neighbors.

Approach

1. Keep a sorted list of [start, end] intervals.
2. For each book(start, end), use binary search to find insertion point.
3. Check overlap with the interval before and after.
4. If no overlap, insert and return true; otherwise return false.

Complexity

• Time: O(n) per book (due to list insertion), O(log n) for search.
• Space: O(n) for stored intervals.

import java.util.*;

class MyCalendar {
    private List<int[]> intervals;

    public MyCalendar() {
        intervals = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        int lo = 0, hi = intervals.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (intervals.get(mid)[0] <= start) lo = mid + 1;
            else hi = mid;
        }
        int i = lo;
        if (i > 0 && intervals.get(i - 1)[1] > start) return false;
        if (i < intervals.size() && intervals.get(i)[0] < end) return false;
        intervals.add(i, new int[]{start, end});
        return true;
    }
}