My Calendar I

class Scheduler {
private:
    set<pair<int, int>> bookings;

public:
    bool reserve(int startTime, int endTime) {
        pair<int, int> newEvent{startTime, endTime};
        auto it = bookings.lower_bound(newEvent);
        if (it != bookings.end() && it->first < endTime) {
            return false;
        }
        
        if (it != bookings.begin()) {
            auto previousEvent = prev(it);
            if (previousEvent->second > startTime) {
                return false;
            }
        }

        bookings.insert(newEvent);
        return true;
    }
};

This C++ solution defines a class Scheduler that facilitates the booking of events without any overlap in their scheduled times. The main functionality is encapsulated within the reserve method, which verifies and allows the addition of new events to a set of booked time intervals.

• The bookings set holds pairs of integers, each pair representing the start and end time of an event. This set automatically keeps the entries sorted by their start times.
• The reserve method checks if there is any overlap with other existing bookings before inserting a new entry:
  1. Construct a pair newEvent from the provided startTime and endTime.
  2. Search for potential conflicts using lower_bound to determine where the newEvent would fit within the set based on the start time.
  3. Check against the next pre-existing event found by lower_bound to ensure the new event's end time does not overlap with this event's start time.
  4. Also check the event just before the insertion point (if it exists) to see if its end time overlaps with the start of the new event.
  5. If no overlaps are found, insert the new event into the set.
  6. Return true if the event is successfully booked, and false if the event conflicts with existing bookings.

This solution effectively handles booking queries with time complexity driven largely by set operations, specifically insert and lower_bound, both operating at logarithmic time complexity relative to the number of elements.

class EventScheduler {
    TreeMap<Integer, Integer> events;

    EventScheduler() {
        events = new TreeMap<>();
    }

    public boolean schedule(int start, int end) {
        Integer previous = events.floorKey(start),
                upcoming = events.ceilingKey(start);
        if ((previous == null || events.get(previous) <= start) &&
                (upcoming == null || end <= upcoming)) {
            events.put(start, end);
            return true;
        }
        return false;
    }
}

The "My Calendar I" implementation involves creating a scheduling system where non-overlapping events can be added, and implemented in Java using a TreeMap. Below is a breakdown of the provided solution:

• Define the EventScheduler class with a private TreeMap named events to manage the events. The keys of this map are the start times of events, and the values are their corresponding end times.

• The constructor EventScheduler() initializes the events TreeMap.

• Implement the schedule() method to add new events:

  1. Use TreeMap.floorKey() to locate the largest key less than or equal to the current start time.
  2. Use TreeMap.ceilingKey() to find the smallest key greater than or equal to the start time.
  3. Check for overlaps:
  • Ensure the event ending before the current start time either does not exist or finishes before the new event starts.
  • Make sure there is no existing event starting before the current event ends.
  1. If no overlap occurs, insert the new event into the events map with the start time as the key and the end time as the value, then return true.
  2. If an overlap is detected, return false to indicate the event cannot be scheduled.

This solution efficiently checks for event overlap and maintains ordered events ensuring that any scheduling or querying operations are handled optimally.

from sortedcontainers import SortedList

class Scheduler:
    def __init__(self):
        self.appointments = SortedList()

    def make_booking(self, start_time: int, end_time: int) -> bool:
        position = self.appointments.bisect_right((start_time, end_time))
        if (position > 0 and self.appointments[position-1][1] > start_time) or (position < len(self.appointments) and self.appointments[position][0] < end_time):
            return False
        self.appointments.add((start_time, end_time))
        return True

The problem "My Calendar I" involves building a scheduler that manages time-based appointments without overlapping. The solution is implemented in Python 3 using the SortedList from the sortedcontainers module which ensures automatic sorting and offers fast insertion times.

Here's how the provided solution operates:

• Initially, define a Scheduler class with an appointments attribute, a SortedList that holds confirmed appointments as tuples of (start_time, end_time).

• The make_booking method handles the booking process:

  • Calculate the insertion position using bisect_right to find the appropriate spot in the sorted list for the new appointment.
  • Check existing appointments around this position to prevent overlaps:
    • If there's an appointment before the current spot that ends after the new appointment begins, reject the booking.
    • If there's an appointment after the current spot that starts before the new appointment ends, reject the booking.
  • If no overlaps are found, add the new appointment to the list using .add(), and confirm the booking by returning True.

This implementation efficiently manages appointments by leveraging the sorted nature of SortedList, achieving fast query and insertion times, crucial for applications dealing with large datasets or requiring prompt responses.