Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum.

Now I'm not sure if a greedy algorithm will do the trick. That is, sort by cost and always take the next job that doesn't intersect and with max cost between the two.

Is this equivalent to a knapsack problem? How could I approach it?

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver.

There are a number of special cases of perfect graphs for which people have discovered simpler and more efficient algorithms for this task. I don't know whether interval graphs fall into one of these special cases.

StackExchange Computer Science Q#11265, answer score: 8