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?
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., [1] for details and discussion.



[1] Hsiao, Ju Yuan, Chuan Yi Tang, and Ruay Shiung Chang. "An efficient algorithm for finding a maximum weight 2-independent set on interval graphs." Information Processing Letters 43.5 (1992): 229-235.