Участник:Alexryabov/TaskMinimumNumberOfRefuelingStops

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/minimum-number-of-refueling-stops

 
from heapq import heapify,heappush,heappop
 
class Solution(object):
    def minRefuelStops(self, target, startFuel, stations):
        priority_queue = []
        currentFuel = startFuel
        answer = 0
        # Если начального топлива хватит до конца без дозаправки, то сразу выдаем ответ
        if startFuel >= target:
            return 0
        previous_station_location = 0
        # Пункт назначения добавляем как станцию
        stations.append((target, float('inf')))
        for current_station in stations:
            # доехали до станции = потратили топливо на перемещение между двумя соседними станциями
            currentFuel -= (current_station[0] - previous_station_location)
            while currentFuel < 0: # если топлива не хватило, значит надо заправиться "задним числом"
                if priority_queue:
                    currentFuel += -heapq.heappop(priority_queue)
                    answer += 1
                else: # в очереди для заправки нет станций, а заправиться надо = фиаско
                    return -1
            heapq.heappush(priority_queue, -current_station[1])
            previous_station_location = current_station[0]
        return answer