Leetcode-problem-resolution/Minimum Number of Refueling Stops at master · DoesLin/Leetcode-problem-resolution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class Solution {
public:
	int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
		if (startFuel >= target)
		{
			return 0;
		}
		else if (stations.size() == 0)
		{
			return -1;
		}

		map<int, int> num_refuel_target;
		set<vector<int>> unvisited_station = set<vector<int>>(stations.begin(), stations.end());
		bool cant_arrived = false;
		int num_refuel = 0;
		num_refuel_target.insert(make_pair(num_refuel, startFuel));
		int prev_refuel_target = startFuel;
		auto prev_station = stations[0];

		while (unvisited_station.size() != 0 && !cant_arrived)
		{
			cant_arrived = true;
			num_refuel++;
			for (auto station : stations)
			{
				if (unvisited_station.find(station) == unvisited_station.end())
				{
					continue;
				}
				auto it = num_refuel_target.find(num_refuel - 1);
				if (it->second >= station[0])
				{
					cant_arrived = false;
					auto cur_it = num_refuel_target.find(num_refuel);
					if (cur_it == num_refuel_target.end())
					{
						num_refuel_target.insert(make_pair(num_refuel, it->second + station[1]));
						unvisited_station.erase(station);
						prev_station = station;
					}
					else
					{
						prev_refuel_target = cur_it->second;
						cur_it->second = max(cur_it->second, it->second + station[1]);
						if (prev_station[1] > station[1])
						{
							continue;
						}
						unvisited_station.insert(prev_station);
						unvisited_station.erase(station);
						prev_station = station;
					}
				}
				if (num_refuel_target.rbegin()->second >= target)
				{
					return num_refuel_target.rbegin()->first;
				}
			}
		}

		return -1;
	}
};