Why does the hint say "In Python this question might be much harder than usual"?


  • 0
    I

    In hint it says that:

    Treat each interval [start, end) as two events "start" and "end", and process them in sorted order. (In Python this question might be much harder than usual.)

    Why does the hint say "In Python this question might be much harder than usual"?


  • 1

    @imsure Do you know a Python Solution? I don't (except for something complicated like a segment tree.) Certainly not in line with the other simpler solutions posted here in C++ and Java.


  • 0
    I

    @awice I see your point. Python doesn't have data structure similar with std::map in C++ or TreeMap in Java. The following Python code works, but too inefficient.

    from collections import OrderedDict
    
    class MyCalendarThree:
    
        def __init__(self):
            self.maxBooking = 0
            self.booking = {}
    
        def book(self, start, end):
            """
            :type start: int
            :type end: int
            :rtype: int
            """
            self.booking[start] = self.booking.get(start, 0) + 1
            self.booking[end] = self.booking.get(end, 0) - 1
            ordered = OrderedDict(sorted(self.booking.items(), key=lambda t: t[0]))
            booked = 0
            for k in ordered:
                booked += ordered[k]
                self.maxBooking = max(self.maxBooking, booked)
    
            return self.maxBooking
    

  • 1
    G

    @imsure Thank you for sharing your idea with us. I think your idea for this problem is straightforward and clear to understand. I added a sorted list to maintain the right order of the dict as the code below. It passed the test without time limit exceeds. But I'm sure there is more room for improvement.
    class MyCalendarThree(object):

    def __init__(self):
        self.maxBooking = 0
        self.booking = {}
        self.sorted_pos = [] # added a sorted list for indexing the dict
    
    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: int
        """
        import bisect
        self.booking[start] = self.booking.get(start, 0) + 1
        self.booking[end] = self.booking.get(end, 0) - 1
        
        # added a sorted list for indexing the dict
        pos_start = bisect.bisect_left(self.sorted_pos, start)
        if not self.sorted_pos or pos_start > len(self.sorted_pos) - 1 or self.sorted_pos[pos_start] != start:
            bisect.insort_left(self.sorted_pos, start)
    
        pos_end = bisect.bisect_left(self.sorted_pos, end)
        if not self.sorted_pos or pos_end > len(self.sorted_pos) - 1 or self.sorted_pos[pos_end] != end:
            bisect.insort_left(self.sorted_pos, end)       
        
        booked = 0
        for k in self.sorted_pos:
            booked += self.booking[k]
            self.maxBooking = max(self.maxBooking, booked)
    
        return self.maxBooking

  • 0
    I

    @gaosuwoniu Looks nice. Thanks for sharing!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.