Apartment hunting

 avatar
user_1884715
python
13 days ago
2.2 kB
3
Indexable
Never
#O(N) time, O(N*R) space
def apartmentHunting(blocks, reqs):
    n = len(blocks)
    r = len(reqs)
    INF = float('inf')
    lastReqIdxFromLeft = generateLeftClosestReq(blocks, reqs)
    lastReqIdxFromRight = generateRightClosestReq(blocks, reqs)
    optimalBuildingIdx = 0
    maxWalkFromOptimalBuilding = INF
    for i in range(n):
        maxWalkFromIthBlock = maxWalkFromBlock(i, lastReqIdxFromLeft[i], lastReqIdxFromRight[i], reqs)
        if maxWalkFromIthBlock < maxWalkFromOptimalBuilding:
            optimalBuildingIdx = i
            maxWalkFromOptimalBuilding = maxWalkFromIthBlock
    return optimalBuildingIdx

def generateLeftClosestReq(blocks, reqs):
    n = len(blocks)
    r = len(reqs)
    INF = float('inf')
    lastReqIdxFromLeft = [{req: INF for req in reqs} for i in range(n)]
    for i, block in enumerate(blocks):
        for req in reqs:
            if block[req] == True:
                lastReqIdxFromLeft[i][req] = i
            elif i > 0:
                lastReqIdxFromLeft[i][req] = lastReqIdxFromLeft[i-1][req]
    return lastReqIdxFromLeft 

def generateRightClosestReq(blocks, reqs):
    n = len(blocks)
    r = len(reqs)
    INF = float('inf')
    lastReqIdxFromRight = [{req: INF for req in reqs} for i in range(n)]
    for i in range(n-1, -1, -1):
        for req in reqs:
            if blocks[i][req] == True:
                lastReqIdxFromRight[i][req] = i
            elif i < n-1:
                 lastReqIdxFromRight[i][req] = lastReqIdxFromRight[i+1][req]
    return lastReqIdxFromRight

def maxWalkFromBlock(i, lastReqIdxFromLeft, lastReqIdxFromRight, reqs):
    INF = float('inf')
    maxWalkFromIthBlock = 0
    for req in reqs:
        leftClosestIdx, rightClosestIdx = lastReqIdxFromLeft[req], lastReqIdxFromRight[req]
        walkForReq = INF
        if leftClosestIdx != INF:
            leftWalk = i - leftClosestIdx
            walkForReq = min(walkForReq, leftWalk)
        if rightClosestIdx != INF:
            rightWalk = rightClosestIdx - i
            walkForReq = min(walkForReq, rightWalk)            
        maxWalkFromIthBlock = max(maxWalkFromIthBlock, walkForReq)
    return maxWalkFromIthBlock
Leave a Comment