Medium

My Calendar I

LAB

Simulate booking half-open intervals [start,end). Return true for accepted bookings and false for overlaps.

EXAMPLES

Example 1

Input
{
  "bookings": [
    [
      10,
      20
    ],
    [
      15,
      25
    ],
    [
      20,
      30
    ]
  ]
}

Output
[
  true,
  false,
  true
]

FUNCTION SHAPE

bookings: intMatrix→boolArray

SOLUTION NOTE

3 solutions: 1. Brute force. O(n). 2. Binary Search. O(logn). 3. Line Sweep. O(n).

Binary search is actually the most efficient, where we find exactly which booking can be overlapping.

However, I recommend learning approach 3, because it will generalize to My Calendar II and III.

Key insight: We use line sweep to count active events at each point. If at any point we have more than one active event, there's an overlap.

Reveal reference solution +

pythonREFERENCE

# 1. Brute force O(n) per book
class MyCalendar:
    def __init__(self):
        self.calendar = []

    def book(self, start, end):
        for s, e in self.calendar:
            if max(s, start) < min(e, end):
                return False
        self.calendar.append((start, end))
        return True

# 2. Binary search O(log n) per book
from sortedcontainers import SortedList

class MyCalendar:
    def __init__(self):
        self.calendar = SortedList()

    def book(self, start, end):
        i = bisect_left(self.calendar, (end, float('-inf')))

        if i == 0 or self.calendar[i-1][1] <= start:
            self.calendar.add((start, end))
            return True
        return False

# 3. Line sweep O(n) per book - GENERALIZES TO MY CALENDAR II AND III
from sortedcontainers import SortedDict

class MyCalendar:
    def __init__(self):
        self.lines = SortedDict()

    def book(self, start, end):
        curr_sum = 0
        if start not in self.lines: self.lines[start] = 0
        if end not in self.lines: self.lines[end] = 0

        self.lines[start] += 1
        self.lines[end] -= 1

        for time in self.lines:
            curr_sum += self.lines[time]
            if curr_sum == 2:  # overlap
                self.lines[start] -= 1
                self.lines[end] += 1
                if self.lines[start] == 0: del self.lines[start]
                if self.lines[end] == 0: del self.lines[end]
                return False

        return True

TimeO(n) for line sweep, O(log n) for binary search

SpaceO(n)

Open on LeetCode ↗