On the street where you live, one evening people had walked to visit friends. At 2am they all decide to go home, but it’s very cold, so all of them call DroneTaxi. You are the owner and operator of DroneTaxi, which uses a helicopter drone to take people to their destination. You have cornered the drone taxi market because everyone else thinks it is too nerdy and you are too competitive, but amazingly they trust your drone to take them home safely. A house may have several people who want to go home, and a house can be the destination of more than one person. The drone can only hold one passenger at a time, and when it picks someone up it takes them straight to their destination. You know the current location and destination of every person, and monitor the drone to
make sure it is performing correctly.
There are n houses and n people have called DroneTaxi. The houses are all in a line, numbered 0 . . . n in order, and adjacent houses are one unit apart. Your headquarters is your house, number 0, and the drone starts there and ends up there once everyone has been taken home. It does not have to come back there between delivering one passenger and getting the next. Unfortunately, since you are a complete nerd no one came to your house to visit, and no one, other than you, has house 0 as their destination.

(a) (7 points) Design an efficient algorithm to fly all of them home, where efficiency is
the worst-case for the total distance flown plus thinking time. Thinking time is the
time it takes to decide on the ordering to pick up the people. Assume your head
runs a serial algorithm to do this (ignoring the massive parallelism of the brain).
Analyze the worst-case time your algorithm takes.

(b) (3 points) For the algorithm you gave in (a), prove that the distance your drone
travels is c-competitive, for some constant c, compared to the optimal route which
must start and end at house 0. The smaller the value of c the better your grade.
If your algorithm isn’t c-competitive for any constant c then prove that.