The following problem was given as an assingment in Introduction to algorithms course:↵
↵
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.↵
↵
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 ofan 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. :)
↵
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.↵
↵
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
↵
Any hints would be very appreciated. :)
