### Create an Account

Home / Questions / Suppose you’ve taken a part-time job where you drive sales executives of a company to clie...

# Suppose you’ve taken a part-time job where you drive sales executives of a company to client sites Each trip starts and ends at the company’s headquarters A sales executive specifies

Suppose you’ve taken a part-time job where you drive sales executives of a company to client sites. Each trip starts and ends at the company’s headquarters. A sales executive specifies a trip by its start and finish times. A trip is specified by a start time s and a finish time f. The start time is when you leave the headquarters for a client site; the finish time is when you get back to the headquarters from the client’s site. In particular, you can drive for the trip[s,f] and then the trip[s′,f′] if and only if f≤s′.

Consider a day in your job. At the beginning of the day, the executives have already requested their trips and there’s n of them:(s1,f1),(s2,f2),...,(sn, fn). For some reason, you’re the only driver or the day so you can’t honor all these requests. Some of the executives will just have to take Uber or Lyft. In addition,you’re paid according to the number of trips you complete. How should you choose which trips to drive?

a. Here’s one possibility–pick the trips according to their length; the shorter they are, the better. It seems smart because shorter trips free you up so you can drive for slightly longer trips.

b. Design a different greedy algorithm that takes(s1,f1),(s2,f2),...,(sn, fn) as input and outputs a subset of these trips that you can drive in a day so that the number of trips is as large as possible. What is the running time of your algorithm?

c. Briefly, argue that your algorithm is correct.

Jun 16 2020 View more View Less