[leetCode] 729. My Calendar I (Python)

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return 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.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

 

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

 

Note:

• The number of calls to MyCalendar.book per test case will be at most 1000.
• In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

첫번째 시도

class MyCalendar:

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

    def book(self, start: int, end: int) -> bool:
        range_list = list(range(start, end))
        
        if len(self.book_state) == 0:
            self.book_state.append(range_list)
            return True
        
        else:
            for book_st in self.book_state:
                if list(set(book_st) & set(range_list)) != []:
                    return False
            self.book_state.append(range_list)
            
            return True

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

입력 받은 start와 end를 통해 range_list를 생성하고 set으로 바꾼 뒤 기존 예약 건인 range_list와 & 연산을 바탕으로

겹치는 시간이 있을 경우 False를 겹치는 시간이 없을 경우 True를 반환하도록 하였습니다.

 

하지만 결과는 긴 입력에 대해서 시간 초과 결과를 얻게 되었습니다.

 

두번째 시도

이번에는 range_list를 생성하지 말고 그냥 start, end를 저장한 후 

새로 들어오려는 start, end 시간과 기존 시간을 비교하여

조건에 부합하면 True 그렇지 않으면 False를 return하도록 했습니다.

class MyCalendar:

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

    def book(self, start: int, end: int) -> bool:
        
        if len(self.book_state) == 0:
            self.book_state.append([start, end])
            return True
        
        else:
            for book_st in self.book_state:
                if start >= book_st[1] or end <= book_st[0]:
                    continue
                else:
                    return False
            self.book_state.append([start, end])
            
            return True

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

두번째 시도는 성공! 하지만 744ms로 매우 속도가 느린 코드임을 알 수 있습니다.

 

이는 추후 1일 1코딩 365일차가 되면! 한번 1년 동안의 코드들 중 비효율적이었던 코드를 다시 풀어보면서

성능을 높여볼 예정입니다.

 

읽어주셔서 감사합니다.

SOMJANG/CODINGTEST_PRACTICE