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](http://ac.els-cdn.com/0166218X87900370/1-s2.0-0166218X87900370-main.pdf?_tid=3919f160-9f48-11e5-9691-00000aacb35f&acdnat=1449757005_d8be70cba06f80d131c51580ab1e3be3) 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.↵
↵
Any hints would be very appreciated. :)
↵
**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](http://ac.els-cdn.com/0166218X87900370/1-s2.0-0166218X87900370-main.pdf?_tid=3919f160-9f48-11e5-9691-00000aacb35f&acdnat=1449757005_d8be70cba06f80d131c51580ab1e3be3) 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.↵
↵
Any hints would be very appreciated. :)
