One question per day (2022-07-02) - Minimum refueling times

871. Minimum refueling times

Problem description ：

Example 1：
Input ：target = 1, startFuel = 1, stations = []
Output ：0
explain ： We can get to our destination without refueling .

Example 2：
Input ：target = 100, startFuel = 1, stations = [[10,100]]
Output ：-1
explain ： We can't get to our destination , Not even getting to the first gas station .

Example 3：
Input ：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output ：2
explain ：
We set out with 10 Liter fuel .
We drove to the starting point 10 The gas station at mile , Consume 10 Liter fuel . Take the gas from 0 To add to 60 l .
then , We from 10 The gas station is miles away 60 The gas station at mile （ Consume 50 Liter fuel ）,
And take the gas from 10 To add to 50 l . Then we drove to our destination .
We are on the way 1 Two gas stations stop , So back 2 .

Their thinking ：

Let's not understand it as a gas station , It's not a gas station on the road , But barrels of oil , Every time I pass , Just take the oil , In order to ensure the minimum refueling times , When the oil is not enough, we take the largest barrel of oil and add , So if you run out of oil , Then it won't arrive
Simply put, it's a straight line , From start to end , Distance from starting point station[i][0] Each location has a capacity of station[i][1] Gasoline barrel , If you can reach the end, return Minimum refueling times , Otherwise return to -1;

Answer key ：

func minRefuelStops(target int, startFuel int, stations [][]int) int {
    
	//  If the oil quantity in the initial state can reach , return 0
	if target <= startFuel {
    
		return 0
	}
	remainOil := startFuel //  The rest of the gasoline 
	pos := make([]int, 0) //  The oil bucket on your body 
	visited := make(map[int]bool) //  Whether the oil drum at this position has been picked up , If it has been picked up , Just ignore it , Otherwise, take it with you .
	ans := 0 //  Refueling times 

	for {
     //  If there is no oil 
		if target > remainOil {
    
			//  Traverse the oil bucket on the road , Pick up passing oil barrels 
			for _, distance := range stations {
    
				//  Current oil volume   You can pass the oil bucket you brought   also   I haven't brought this oil bucket before 
				if remainOil >= distance[0] && visited[distance[0]] != true {
    
					//  The oil bucket with the mark on your body 
					visited[distance[0]] = true
					pos = append(pos, distance[1])
				}
			}
			//  because   When we get here   signify  target > remainOil
			// len(pos) == 0： At this time, if there is no oil bucket to pick up on the road 
			//  Represents the end of the journey , The destination cannot be reached .
			if len(pos) == 0 {
    
				return -1
			}
			sort.Ints(pos)
			remainOil = remainOil + pos[len(pos)-1]
			ans++
			//  This oil bucket has been used   Just throw it away 
			pos = pos[:len(pos)-1]
		} else {
    
			return ans
		}
	}
}

Submit results ：