algoadvance

You are implementing a program to manage a calendar of events. Each event is defined by two integers: a start time and an end time. Implement the MyCalendar class:

1. MyCalendar(): Initializes the calendar object.
2. bool book(int start, int end): Attempts to book an event from start to end (exclusive). If there is no conflicting event that overlaps with this time range, the event can be booked and the method returns True. Otherwise, the method returns False.

Clarifying Questions

1. Event Boundaries: Is the end time inclusive or exclusive? This is important for determining overlaps.
   • The end time is exclusive.
2. Time Range: What is the range of possible values for start and end?
   • The range for start and end is not explicitly stated but will likely be within a manageable size for memory and computational purposes.
3. Concurrent Calls: Will the calendar system handle concurrent calls?
   • Assume no concurrency issues (synchronous single-threaded environment).

Strategy

To solve this problem, we’ll keep a list to store the intervals of the booked events. For each new booking, we will:

1. Iterate through the list of booked events.
2. Check for any overlap with the new event.
   • An overlap occurs if start < booked_event_end and end > booked_event_start.
3. If an overlap is found, return False.
4. If no overlap is found after checking all booked events, add the new event to the list and return True.

This approach ensures that we accurately manage overlapping events while maintaining the simplicity.

Code

class MyCalendar:

    def __init__(self):
        # Initialize the list to store booked intervals
        self.booked = []

    def book(self, start: int, end: int) -> bool:
        # Check for overlap with existing bookings
        for s, e in self.booked:
            if start < e and end > s:
                return False
        # If no overlap, book the event
        self.booked.append((start, end))
        return True

Time Complexity

• The time complexity for each book call is O(n) in worst case, where n is the number of currently booked events. This is because we need to check every existing booking for potential overlaps.
• Space complexity is O(n) since we store each booking.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?