(2) (Trip refueling) (25 points) Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station. Design a greedy algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time. Prove that your algorithm finds an optimal sequence of stops. (2) (Trip refueling) (25 points) Suppose you want to travel from city A to city B by car, following a fixed route. Your car can travel m miles on a full tank of gas, and you have a map of the n gas stations on the route between A and B that gives the number of miles between each station. Design a greedy algorithm to find a way to get from A to B without running out of gas that minimizes the total number of refueling stops, in O(n) time. Prove that your algorithm finds an optimal sequence of stops