2532.md

2532. Time to Cross a Bridge

Solution 1 (time O(nlogk), space O(k))

class Solution(object):
    def findCrossingTime(self, n, k, time):
        """
        :type n: int
        :type k: int
        :type time: List[List[int]]
        :rtype: int
        """
        time.sort(key=lambda x: x[0] + x[2])
        cur_time, remain = 0, n
        wait_left = [-i for i in range(k - 1, -1, -1)]
        wait_right = []
        work_left = []
        work_right = []
        while remain > 0 or wait_right or work_right:
            while work_left and work_left[0][0] <= cur_time:
                p = heapq.heappop(work_left)
                heapq.heappush(wait_left, -p[1])
            while work_right and work_right[0][0] <= cur_time:
                p = heapq.heappop(work_right)
                heapq.heappush(wait_right, -p[1])
            if wait_right:
                i = -heapq.heappop(wait_right)
                cur_time += time[i][2]
                heapq.heappush(work_left, [cur_time + time[i][3], i])
            elif remain > 0 and wait_left:
                i = -heapq.heappop(wait_left)
                cur_time += time[i][0]
                heapq.heappush(work_right, [cur_time + time[i][1], i])
                remain -= 1
            else:
                next_time = float("inf")
                if work_left:
                    next_time = min(next_time, work_left[0][0])
                if work_right:
                    next_time = min(next_time, work_right[0][0])
                if next_time != float("inf"):
                    cur_time = next_time
        return cur_time