My Calendar I[Array,Binary Search,Design,Segment Tree,Ordered Set]

https://leetcode.com/problems/my-calendar-i/description/?envType=daily-question&envId=2024-09-26

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

• MyCalendar() Initializes the calendar object.
• boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

 

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

 

Constraints:

• 0 <= start < end <= 109
• At most 1000 calls will be made to book.

문제부터 구구절절 넘 길었지만,

읽어보면 그렇게 어려울 거 까진 없을 거 같은 문제.

근데 Topic에 Binary Tree가 있는 걸로 봐서, 또 testcase로 겁나 복잡한 거 던져줄 거 같다.

 

1. Python

굉장히 Naive하게 접근..

class MyCalendar:

    def __init__(self):
        self.s = set()
    def book(self, start: int, end: int) -> bool:
        if not self.s :
            for i in range(start,end):
                self.s.add(i)
            return True
        else :
            for j in range(start,end):
                if j in self.s:
                    return False
            for k in range(start,end):
                self.s.add(k)
            return True

# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

 

역시나 일반적인 Test case는 다 통과가 되는데 무지막지하게 길게 만들어버린 test case에선 Memory limit이 걸린다..

 

복잡한 Bianry Search의 세계.. Time Complexity가 O(N) -> O(log N)만 되어도 차이가 엄청나는구먼

 

class MyCalendar:

    def __init__(self):
        self.bookings = []

    def book(self, start: int, end: int) -> bool:
        low, high = 0, len(self.bookings)

        # Perform binary search to find the correct insert position
        while low < high:
            mid = (low + high) // 2
            if self.bookings[mid][0] < end:
                low = mid + 1
            else:
                high = mid

        # Check for overlap with the previous interval
        if low > 0 and self.bookings[low - 1][1] > start:
            return False

        # Check for overlap with the next interval
        if low < len(self.bookings) and self.bookings[low][0] < end:
            return False

        # Insert the new booking at the correct position
        self.bookings.insert(low, (start, end))
        return True

# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

 

Tree로 푸는 방법도 있다..

class LinkedList:
    def __init__(self,val, next):
        self.val = val
        self.next = next
    
class MyCalendar:

    def __init__(self):
        self.dummy = LinkedList([0,0], None)

    def book(self, start: int, end: int) -> bool:
        curr = self.dummy
        prev = None
        while curr and curr.val[1] <= start:
            prev = curr
            curr = curr.next
        if curr == None:
            prev.next = LinkedList([start, end], None)
        else:
            if curr.val[0] >= end:
                node = LinkedList([start, end], None)
                prev.next = node
                node.next = curr
            else:
                return False
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

 

2. C++

#include <iostream>
#include <vector>
using namespace std;

class MyCalendar {
public:
    MyCalendar() {}
    
    bool book(int start, int end) {
        int low = 0;
        int high = bookings.size();

        // Binary search to find the correct position to insert
        while (low < high) {
            int mid = (low + high) / 2;
            if (bookings[mid].first < end) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        // Check for overlap with the previous interval
        if (low > 0 && bookings[low - 1].second > start) {
            return false;
        }

        // Check for overlap with the next interval
        if (low < bookings.size() && bookings[low].first < end) {
            return false;
        }

        // Insert the new booking
        bookings.insert(bookings.begin() + low, {start, end});
        return true;
    }

private:
    vector<pair<int, int>> bookings;
};

int main() {
    MyCalendar cal;
    cout << cal.book(10, 20) << endl;  // Expected output: 1 (true)
    cout << cal.book(15, 25) << endl;  // Expected output: 0 (false)
    cout << cal.book(20, 30) << endl;  // Expected output: 1 (true)
    return 0;
}