Python - Intervals Based Problem - Max Heap ✅
I was not able to come up with an optimal solution myself. I had to look at the discussion section but I hardly found any solution that had a good explanation f
I was not able to come up with an optimal solution myself. I had to look at the discussion section but I hardly found any solution that had a good explanation for the Max Heap approach.\n\nSo, after spending almost 2 hours understanding the approach, I will try my best to explain what is going on here.\n\nSee, first, we need to understand some things before we move on to Max Heap approach.\n\nLet\'s take an example.\n\n\tSuppose, we have 10 seats.\n\t\n\tNow, if a person comes, he should sit at seat "0" since no seat is occupied.\n\t\n\tAnother person comes. He should sit at seat "9" that is the last seat.\n\t\n\tNow, we have this interval [0,9] where "0" and "9" have person sitting\n\tAnd between these two, all the seats are available\n\t\n\tSo, next time a person comes, we can avoid manually checking each seat to see which is optimal one.\n\t\n\tWhen seats "0" and "9" are occupied, there are two seats that have same maximum closest distance\n\tThose are seats "4" and "5".\n\t\n\tFor seat "4", the closest occupied seat is seat "0" and so distance is "4"\n\tSimilarly For seat "5", the closest occupied seat is seat "9" and so distance is "4"\n\t\n\tBut, as the problem statement says, we have to choose the seat that has a smaller number.\n\tSo here, the person should sit at seat "4".\n\t\n\tNow, you can quickly get this optimal seat for any interval by just doing floor of (left+right) / 2\n\t\n\tHere, floor of (0 + 9)/2  => floor of 4.5 => 4 => MOST OPTIMAL SEAT for interval [0,9]\n\t\nSo, quickly finding the most optimal seat is one thing we need to figure out.\n\n\tNow that a person sits at seat "4" it means, the interval [0,9] is no longer valid\n\tBecause remember, an interval [left,right] means all seats between left and right are empty.\n\t\n\tSo, now that seat "4" is occupied, this means we now have two new intervals.\n\t\n\t[0,4] and [4,9]\n\t\n\tMakes sense, right?\n\t\n\tNow, the next time a person comes, we have to choose the most optimal seat from these two intervals.\n\t\n\tFor interval [0,4], the most optimal seat is floor of (0 + 4) / 2 => seat 2\n\tAnd for interval [4,9] the most optimal seat is floor of (4 + 9) / 2 => seat 6\n\t\n\tNow the thing is, for both the seats, the closest distance is the same.\n\t\n\tFor seat "2" closest occupied seat is "0" so distance => 2\n\tFor seat "6" closest occupied seat is "4" so distance => 2\n\t\n\tBut again, we have to choose the lower seat number.\n\t\n\tNow that seat "2" is occupied as well, it means interval [0,4] is no longer valid\n\tAnd now, two new intervals are there\n\t\n\t[0,2] and [2,4]\n\t\n\tThe issue now is, for large test cases, at any time, there can be a lot of intervals\n\tSo, we cannot just go over every single interval, \n\tget the most optimal seat, get the closest distance and so on\n\t\n\tWe somehow need a way such that at any time, we can pick that one interval \n\tfor which the closest distance is maximum. And even if multiple intervals have same distance\n\tthe interval that appears first is chosen.\n\t\nAnd that\'s where a Max Heap comes into the picture.\n\t\nWe can put our intervals in a Max heap which will order them based on the distance between most optimal seat and the seat closest to that most optimal seat. \n\n\tFor any interval we choose, we can not only find the most optimal seat but we can quickly find the closest distance as well.\n\t\n\tFor example, if we have interval [0,4]\n\t\n\tthe most optimal seat is floor of (0 + 4) / 2 => floor of (2) => 2\n\t\n\tAnd the closest distance is between "2" and "0" => 2\n\t\n\tThis can be calculated as floor of (4 - 0) / 2 => floor of 2 => 2\n\t\nAnd well, that\'s all we need to know before we start writing the code.\n\nNote that there will be some edge cases while calculating the most optimal seat and closest distance.\n\n\tFor example,\n\t\n\tInitially when no seat is occupied, the whole row from 0 to 9 is available\n\t\n\tIt means, the interval is [-1,10]\n\t\n\tSo, here, as per our formula, most optimal seat is floor of (-1 + 10) / 2 => floor of (9/2) => floor of 4.5 => 4\n\t\n\tBut that\'s wrong. Since all sets are empty, the most optimal is seat "0".\n\t\n\tAnd similarly, the formula for closest distance is floor of (10 - (-1)) / 2 -> floor of 11/2 => 5\n\tBut, the closest distance is actually "0" because there is no seat occupied yet apart from seat "0"\n\tSo there is no distance value yet.\n\t\n\tSo, that\'s one edge case.\n\n\tNow, suppose person sits at seat "0".\n\t\n\tNow, there will again be two new intervals [-1,0] and [0,10]\n\t\n\tFor interval [-1,0] the closest distance is "0" because "left" is -1\n\t\n\tIn fact, for any interval that starts with -1, the closest distance will be "right" value\n\tFor example if we have [-1,5] or [-1,4] and so on...\n\t\n\tBecause it makes sense right? If we have [-1,5] then the most optimal seat is "0" (since left is -1)\n\tand it will have closest occupied seat at number "5". So distance will be "5 - 0" => 5\n\t\n\tSimilarly, for interval [0,10] most optimal seat as per our formula is floor of (0 + 10) / 2 => 5\n\t\n\tBut, "10" here is the number of seats available. It means, "10" is not even a valid seat number.\n\tIt just means that right now, we just have a person sitting at seat "left" which here is seat "0".\n\t\n\tSo, in this case, the most optimal seat is at "9". \n\t\n\tAnd that\'s another edge case to take care of.\n\n\tAnd similarly, when we calculate the closest distance in this case, we don\'t do floor of (10 - 0) / 2\n\t\n\tAs that will again give is 5. \n\n\tRather, since the most optimal seat is "9", the closest distance will be "9 - 0" => 9 (Or 10 - 0 - 1)\n\t\n\tSo, for any interval that has "right" value as "n" or the number of seats,\n\tThe most optimal seat is "n - 1"\n\tand the closest distance is "n - 1 - left"\n\nSo far, I have talked about the scenario when a person sits at a seat.\n\nWhat about leaving?\n\n\tSuppose, we have three people sitting. So, "0", "4" and "9" are occupied.\n\n\tNow, person "4" leaves.\n\n\tIt means that now, the intervals [0,4] and [4,9] are no longer valid because "4" is now empty.\n\t\n\tSo, we have to remove these intervals from our Max Heap, that is, \n\tremove the interval starting with "4" and the one ending with "4"\n\t\n\tAnd once we do that, it now means the interval [0,9] is again a valid interval so we should push it back in the max heap.\n\t\n\tAnd again, we have to calculate the closest distance by the same logic.\n\t\nAnd well, that\'s the whole approach explained.\n\nI hope I was able to explain the Max Heap solution in detail. Still, if you have any doubts, please comment below. I will try to answer if I can.\n\n```\nclass ExamRoom:  \n\n    def __init__(self, n: int):\n        # Number of seats\n        self.n = n\n        \n        # Max Heap\n        self.maxHeap = []        \n\n    def seat(self) -> int:\n        \n        # If heap is empty, then the whole row of seats is an available interval to us\n        if not self.maxHeap:\n            # left and right boundaries of this interval\n            left,right = -1, self.n\n        \n        # Otherwise, we take the interval with the maximum distance between left and right boundaries\n        # Note that here, boundaries simply mean at "left" and "right" indices, seats are occupied\n        # And between these indices, there are available seats\n        else:\n            top = heappop(self.maxHeap)\n            left,right = top[1], top[2]\n            \n            \n        # Now that we have "left" and "right", let\'s decide at what seat person will sit\n        \n        # If all seats are empty, sit at the seat 0\n        if left == -1: seat = 0\n            \n        # If a person is sitting at "left" index but there is no occupied seat on "right", \n        # Sit at right most seat, that is, n - 1\n        elif right == self.n: seat = self.n - 1\n            \n        # If seat "left" and "right" are occupied\n        # Sit at "floor of (left + right / 2)" seat\n        else: seat = (left + right) // 2\n            \n        # Now that we know at what "seat" person will sit, two new intervals will be created\n        # First is from "left" to "seat" and the other is from "seat" to "right"\n        # So we push these two intervals to the Max Heap \n        # The deciding value based on which these intervals will be ordered is closest distance\n        # So, for interval [left,seat] this distance is floor(seat - left / 2)\n        # For the interval [seat,right] this distance is floor(right - seat / 2)\n        \n        # Closest Distance for the Left Interval => [left,seat]\n        closestDistanceForLeftInterval = (seat - left) // 2\n        \n        # If "left" is -1 then the most optimal seat is seat "0"\n\t\t# And since interval is [left,seat] the closest distance will be "seat" only\n        if left == -1: closestDistanceForLeftInterval = seat\n        \n        # Closest Distance for the Right Interval => [seat,right]\n        closestDistanceForRightInterval = (right - seat) // 2\n        \n        # If "right" is "n" then the interval is [seat, n]\n        # So, for this interval, the most optimal seat is the seat n - 1\n        # So, the distance from most optimal seat to the "seat" will be "self.n - 1 - seat"\n        if right == self.n: closestDistanceForRightInterval = self.n - 1 - seat\n\n        # Push these two intervals in the maxHeap\n        heappush(self.maxHeap, [-closestDistanceForLeftInterval, left, seat])\n        heappush(self.maxHeap, [-closestDistanceForRightInterval, seat, right])\n        \n        # Return the seat number at which student will sit\n        return seat\n        \n\n    def leave(self, p: int) -> None:\n        \n        # Now, just imagine what happens when a person leaves a seat\n        # For example, if at any point, we have three person sitting in a row of 10 seats\n        # Then seats "0", "4" and "9" will be occupied\n        # And if person "4" leaves, it means, \n\t\t# we should now remove the intervals from maxHeap which either start with "4" or end with "4"\n        # Because those intervals are no longer valid now that the seat "4" itself is empty\n        \n        intervalStartsAtP = None\n        intervalEndsAtP = None\n        \n        # Let\'s just loop over the maxHeap since it is just a list internally\n        for interval in self.maxHeap:\n            # If this interval starts with "p"\n            # This should be removed\n            if interval[1] == p: intervalStartsAtP = interval\n            \n            # If this interval ends with "p"\n            # This should be removed\n            if interval[2] == p: intervalEndsAtP = interval\n                \n        # Remove the two\n        self.maxHeap.remove(intervalStartsAtP)\n        self.maxHeap.remove(intervalEndsAtP)\n                \n        # And now, the order is not proper so we have to manually call heapify here\n        heapify(self.maxHeap)\n        \n        # Finally, since we remove the two intervals, it means a bigger interval is now available to us\n        # Imagine that the two intervals we removed are [left, p] and [p, right]\n        # So, it means [left,right] is now a new larger interval available to us, right?\n        # So, put it in the heap\n        left = intervalEndsAtP[1]\n        right = intervalStartsAtP[2]\n        \n        # The same logic to get the closest distance as in seat() method\n        closestDistance = (right - left) // 2\n        \n        # If "left" is -1 then the most optimal option is seat "0"\n        # It means, if next person sits at seat "0", the closest seat will be at "right"\n        # So closest distance here is "right"\n        if left == -1: closestDistance = right\n            \n        # If "right" is "n" then the interval is [left, n]\n        # So, for this interval, the most optimal seat is the seat n - 1\n        # So, the distance from most optimal seat to the "left" will be "self.n - 1 - left"\n        elif right == self.n: closestDistance = self.n - 1 - left\n        \n        # Push this interval in the maxHeap with its closest distance value\n        heappush(self.maxHeap, [-closestDistance, left, right])\n```
['Heap (Priority Queue)', 'Python']