# Constraint Satisfaction: maximizing total value with no overlaps

Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value. Out of all the bars available, we want to choose the set which maximizes the total value but with no overlap between the start points and end points of the bars. In the example above, the selected bars would be the following (in red): What would be the best way to approach this problem computationally, for n number of bars being potentially large (several thousands) and [x,y] the possible bar positions being large as well?

I thought of a probabilistic approach, but are there deterministic approaches as well?

• I am familiar with the deterministic approach. Could you please share the probabilistic approach you thought of, I'd like to compare it with probabilistic earliest deadline first. Thank you. – E. Douglas Jensen Nov 16 '17 at 20:27
• @E.DouglasJensen sorry for late answer — it consists of stochastically building a tree of admissible solutions (pick a random element, then pick another one with no conflict, etc), and once we have enough of them, pick the solution with max value. Obviously, this does not guarantee an optimal solution, but for certain cases it can work very well. – Jivan Nov 25 '17 at 19:50

## 1 Answer

You are looking for a maximum weight independent set in an interval graph, which can be solved in linear time (by a deterministic algorithm). By the way, the same is true also for a superclass of interval graphs, namely chordal graphs.

One such algorithm is based on dynamic programming, you can see e.g.,  for details and discussion.