The following problem was given as an assingment in Introduction to algorithms course:

Raw problem description:

You are given n intervals on real line (integer coordinates) and you have to choose a subset M such that at most k intervals from this subset pairwise intersect (intersection at endpoints doesn't count). Weight w_i of the interval [s_i, e_i] is defined as e_i - s_i. The goal is to find a subset M with maximal sum of interval weights.

Short story:

And since we all prefer a story over raw problem description, even if it is just a short one: :)

Imagine that you are a bus driver driving a bus with exactly k seats. Your bus route contains m stations and you are driving in the direction from station number 1 to station number m. There are a few passengers that would really like to travel with you (n to be exact), where each of them has a start station s_i and an end station e_i. The price i-th passenger will have to pay for the ticket is e_i - s_i.

You as a bus driver can decide which passengers can enter the bus and which of them can not (once a passenger enters the bus you cannot throw him off earlier then at his end station).

What is the maximum price the passengers will pay for the tickets if you choose them optimally?

General solution:

I am aware of a solution of a more general problem, where weights of intervals can be arbitrary. But since this problem was presented at Introduction of algorithms course I guess there has to be a simpler solution for this more specific case.

O(n³) implementation of a solution described in the paper is available 14799130

Any hints would be very appreciated. :)