if you could give it in R code or psuedocode that would be best! thanks! Your fr

Question

if you could give it in R code or psuedocode that would be best! thanks!

Your friend is taking a trip from Anchorage (Alaska) to Rio de Janeiro (Brazil) by airplane. However, a direct flight between those two cities is not an option because your friend gets severely airsick and is restricted to flights of 30 minutes long. Your friend desires to minimize the total number of flights that are needed to complete the journey from Anchorage to Rio de Janeiro. While flight bookings can only be made when at the departing airport, you do already know the flight time each potential airport you could stop at is from Anchorage. For simplicity assume that you can arrange all the potential airports in a straight line from Anchorage to Rio de Janeiro, sorted by the total travel time from Anchorage. Ignore waiting time between flights. Create a greedy algorithm to solve this problem for your friend, letting the sorted travel times be 0 to Sti s . S tn where the subscript indicates a specific city, and city 0 and city n are Anchorage and Rio de Janeiro, respectively. Use all times to be in minutes, and tn-30 hours. Use precise mathematical notation to express your answers

Explanation / Answer

/* what I get it from the question is */

Anchorage ----> Rio

now conditions

1) friend can't take flights who took more than 30 minutes

2) minimize the number of flights

we have given travel time from Anchorage to each city

t0 t1 t2 ........tn

t0 is Anchorage and tn is Rio

/* greedy algorithm

--> we have given sorted travel time

--> reach at farthest city ti which took <=30 minutes

-->then from ti again travel to city tj which is farthest but reachable in less than 30 minutes from ti

repeat until reached tn .

*/

/*

Example :-

number of cities :- 6

time is in minutes

total_travel_time;

total_flights

source destination

t0 t1 t2 t3 t4 t5 t6

0 10 20 50 60 80 100

now starting from t0

by algo find farthest city which can be reachable within 30 minutes

so we can reach at two cities - { t1, t2} - t1 - 10 and t2 - 20

so farthest one is t2 - 20 minutes

total_travel_time += 20;

toatl_flights += 1;

now from t2 we can reach at - {t3 - 30 minutes (50-20) )

total_travel_time += 30;

toatl_flights += 1;

now from t3 we can reach at - {t5 - 30 minutes (80-50) )

total_travel_time += 30;

toatl_flights += 1; ( = 3)

now from t5 we can reach at - {t6 - 20 minutes (100-80) )

total_travel_time += 30; ( =100)

toatl_flights += 1; ( = 4)

destination reached;

*/

/* pseudo code

int main(){

int num_of_cities;

cin>>num_of_cities;

int time[num_of_cities+1] //travel_time from Anchorage

for(int i=0; i<num_of_cities; i++)

cin>>time[i]; //already sorted by distance from Anchorage

int total_travel_time = 0, total_flights = 0;

int current_city = 0,farthest = 0,depart_city = 0;

while(current_city != num_of_cities){

while(current_city < num_of_cities && farthest+time[current_city]-time[depart_city] <= 30){

current_city+=1;

}

total_travel_time += farthest;

farthest = 0;

toatl_flights+=1;

depart_city = current_city;

}

cout<<total_flights<<" ";

}

*/

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.