CareerCup

Suppose we are given a set L of n line segments in the plane, where the endpoints of each
segment lie on the unit circle x^2 + y^2 = 1, and all 2n endpoints are distinct. Describe
and analyze an algorithm to compute the largest subset of L in which no pair of segments
intersects.

You are driving a bus along a highway, full of rowdy, hyper, thirsty students and a soda fountain
machine. Each minute that a student is on your bus, that student drinks one ounce of soda. Your
goal is to drop the students off quickly, so that the total amount of soda consumed by all students
is as small as possible.

You know how many students will get off of the bus at each exit. Your bus begins somewhere
along the highway (probably not at either end) and move s at a constant speed of 37.4 miles per
hour. You must drive the bus along the highway; however, you may drive forward to one exit then
backward to an exit in the opposite direction, switching as often as you like. (You can stop the
bus, drop off students, and turn around instantaneously.)

Describe an efficient algorithm to drop the students off so that they drink as little soda as
possible. Your input consists of the bus route (a list of the exits, together with the travel time
between successive exits), the number of students you will drop off at each exit, and the current
location of your bus (which you may assume is an exit).

I gave a recursive solution but he insisted on dynamic programming which i couldn't give