We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

My Calendar I

Number: 729

Difficulty: Medium

Paid? No

Companies: Uber, Google, Amazon, Oracle, Flexport, Bloomberg, TikTok, Microsoft, Apple

Problem Description

Implement a calendar system that supports adding new events defined by a start and end time. A new event can be booked only if it does not overlap with any existing event in the calendar.

Key Insights

  • Use a list (or array) to store currently booked time intervals.
  • An event [start, end) does not conflict with another if its end time is less than or equal to the other's start time or its start time is greater than or equal to the other's end time.
  • With at most 1000 booking attempts, a simple linear scan for overlapping intervals is acceptable.
  • Optionally, for efficiency or scalability, maintain the intervals in a sorted order and use binary search, checking only immediate neighbors for overlaps.

Space and Time Complexity

Time Complexity: O(n) per booking in the worst-case scenario, where n is the number of existing events.
Space Complexity: O(n), as all events are stored.

Solution

The solution maintains a list of tuples (or pairs) representing booked events. When booking a new event, iterate through the list to check if the new interval overlaps with any already booked interval. The overlap condition is evaluated by ensuring that for every booked interval [s, e), the new event [start, end) satisfies (end <= s or start >= e). If it does, append the new event and return true. If there is any overlap, return false without adding the event.

Code Solutions

# Python implementation for My Calendar I

class MyCalendar:
    def __init__(self):
        # List to store booked intervals as (start, end) tuples
        self.bookings = []
    
    def book(self, start: int, end: int) -> bool:
        # Check each existing booking for an overlap
        for s, e in self.bookings:
            # If new event overlaps with existing event, return False
            if not (end <= s or start >= e):
                return False
        # Could not find overlap, so add the new event
        self.bookings.append((start, end))
        return True

# Example usage:
# myCalendar = MyCalendar()
# print(myCalendar.book(10, 20))  # True
# print(myCalendar.book(15, 25))  # False
# print(myCalendar.book(20, 30))  # True
← Back to All Questions