# Weighted interval set scheduling problem

Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is maximized. This can be solved in linear time with dynamic programming or memoized recursion.

Is there a version of this problem where intervals are grouped, i.e. interval $$a$$ can only be in the solution if intervals $$b$$ and $$c$$ are also in the solution? By this formulation, there would be a weight associated with each group, or set, of intervals.

The most similar problem I've come across is the exact cover problem, which is NP-Complete, but in this instance we're maximizing weight and all vertices need not be covered.

Any insight will be much appreciated. Thanks!

## 2 Answers

This is equivalent to the maximum weighted independent set problem - given a graph with weighted vertices, find a subset of the vertices such that no two vertices in the subset are adjacent in the graph and the sum of their weights is maximized.

The graph the problem is being solved on is a type of interval graph where each vertex represents a group of intervals and its weight is the sum of the intervals' weights. An edge is drawn between two vertices if one or more of their intervals overlap.

I haven't determined if this formulation is tractable or not. While the problem is NP-hard, we know it can be solved efficiently for certain types of graphs, including interval graphs where each vertex represents a single interval.

Sure, you can define any problem you want. Effectively you would no longer seek a cover of intervals, but a cover of sets, where each set is a union of intervals. Over a discrete set, any set can be expressed as a union of intervals. Thus, this is equivalent to the maximum set packing problem. Consequently, it is NP-hard.

• I'm not looking for a cover though, just a set of non-overlapping intervals, i.e. the solution need not cover anything.
– alan
Apr 28, 2020 at 17:32
• @alan, you're right, sorry, I wasn't thinking clearly -- see edited answer.
– D.W.
Apr 28, 2020 at 19:11