Priority queue

895. Maximum Frequency Stack

https://leetcode.com/contest/weekly-contest-99/problems/maximum-frequency-stack/

import heapq
class FreqStack:
def __init__(self):
        self.cnt = collections.defaultdict(list)
        self.i = 0
        self.heap = []
        heapq.heapify(self.heap)
       
    def push(self, x: int) -> None:
        self.i +=1
        self.cnt[x].append(self.i)
        heapq.heappush(self.heap, (-len(self.cnt[x])*20000-self.i, x))
def pop(self) -> int:
        #key, _ = max(self.cnt.items(), key= lambda x:len(x[1])*20000 + (x[1][-1] if x[1] else 0))
        #self.cnt[key].pop()
        _, key = heapq.heappop(self.heap)
        self.cnt[key].pop()
        return key
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()

857. Minimum Cost to Hire K Workers

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        ratio = [w/q for w, q in zip(wage, quality)]
        ratio, wage, quality = zip(*sorted(zip(ratio, wage, quality)))
        r = ratio[K-1]
        total_q = sum(quality[:K])
        res = r*total_q
        heap = [-i for i in quality[:K]]
        heapq.heapify(heap)
        for i in range(K,len(quality)):
            r = ratio[i]
            total_q += quality[i]+heapq.heappop(heap)
            this_res = total_q*r
            res = min(res, this_res)
            heapq.heappush(heap, -quality[i])
        return res

855. Exam Room

Exam Room - LeetCode

class ExamRoom:
    
    def dist(self, x, y):  # length of the interval (x, y)
        if x == -1:        # note here we negate the value to make it maxheap
            return -y
        elif y == self.N:
            return -(self.N - 1 - x)
        else:
            return -(abs(x-y)//2) 
        
    def __init__(self, N):
        self.N = N
        self.pq = [(self.dist(-1, N), -1, N)]  # initialize heap
        
    def seat(self):
        _, x, y = heapq.heappop(self.pq)  # current max interval 
        if x == -1:
            seat = 0
        elif y == self.N:
            seat = self.N - 1
        else:
            seat = (x+y) // 2
        heapq.heappush(self.pq, (self.dist(x, seat), x, seat))  # push two intervals by breaking at seat
        heapq.heappush(self.pq, (self.dist(seat, y), seat, y))
        return seat
        
    def leave(self, p):
        head = tail = None
        for interval in self.pq:  # interval is in the form of (d, x, y)
            if interval[1] == p:  
                tail = interval
            if interval[2] == p:  
                head = interval
            if head and tail:
                break
        self.pq.remove(head)
        self.pq.remove(tail)
        heapq.heapify(self.pq)  # important! re-heapify after deletion
        heapq.heappush(self.pq, (self.dist(head[1], tail[2]), head[1], tail[2]))

My code got stuck.

class ExamRoom:
def __init__(self, N: int):
        self.dp = [0]*N
        self.heap = []
        heapq.heapify(self.heap)
        ii, jj = 0-len(self.dp)+1, len(self.dp)-1
        heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
        ii, jj = 0, len(self.dp)-1+len(self.dp)-1
        heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
        self.debug=True
def seat(self) -> int:
        if self.debug:print(self.heap)
        if self.dp[0]==0 and False:
            #self.dp[0] = 1
            for i in range(len(self.dp)-1, -1, -1):
                if self.dp[i]==1:
                    jj = i
                    ii = -(i-jj)
                    break
            else:
                ii, jj = 0-len(self.dp)+1, 0
            heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
            return 0
        elif self.dp[-1]==0 and False:
            self.dp[-1] = 1
            for i in range(len(self.dp)-1, -1, -1):
                if self.dp[i]==1:
                    ii = i
                    jj = len(self.dp)-1+(len(self.dp)-1-i)
                    break
            else:
                ii, jj = len(self.dp)-1, len(self.dp)-1+len(self.dp)-1
            heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
            #heapq.heappush(self.heap, (-((len(self.dp)-1)//2)*2*10**9+0,0, len(self.dp)-1))
            return len(self.dp)-1
        else:
            while True:
                _, i, j = heapq.heappop(self.heap)
                if (i==0 and j>len(self.dp)-1) or (i<0 and j==len(self.dp)-1) or (self.dp[i] and self.dp[j] and (j-i>=1 and sum(self.dp[i+1:j]))==0):
                    pass
                else:
                    continue
                #print('pop',i, j)
                if i<0:idx=0
                elif j>len(self.dp)-1:idx = len(self.dp)-1
                else:
                    idx = i+(j-i)//2
                    if self.debug:print(idx)
            
                if self.dp[idx]:continue
                self.dp[idx] = 1
                break
            for ii, jj in [(i,idx), (idx, j)]:
                if jj==0 or ii == len(self.dp)-1:continue
                heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
            return idx
def leave(self, p: int) -> None:
        if p==0:
            self.dp[0] = 0
            for i in range(1, len(self.dp)):
                if self.dp[i]==1:
                    jj = i
                    ii = -i
                    break
            else:
                ii,jj =0-len(self.dp)+1, len(self.dp)-1
            #ii, jj = 0-len(self.dp)-1, 0
            heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
        elif p==len(self.dp)-1:
            for i in range(p-1, -1, -1):
                if self.dp[i]==1:
                    ii = i
                    jj = len(self.dp)-1+(len(self.dp)-1-i)
                    break
            else:
                ii, jj = 0, len(self.dp)-1+len(self.dp)-1
            heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
            self.dp[-1] = 0
        else:
            self.dp[p] = 0
            ii, jj =0 ,0
            for i in range(p-1, -1, -1):
                if self.dp[i]==1:
                    ii = i
                    break
            else:
                ii = p
            for i in range(p+1,len(self.dp)):
                if self.dp[i]==1:
                    jj = i
                    break
            else:
                jj = p
            #print(p,ii,jj)
            heapq.heappush(self.heap, (-((jj-ii)//2)*2*10**9+ii,ii, jj))
# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(N)
# param_1 = obj.seat()
# obj.leave(p)