Given a set of jobs, each consisting of a number of weighted intervals on the real line, and a
positive integer m, we study the problem of selecting a maximum weight subset of the
intervals such that at most one interval is selected from each job and, for any point p on the
real line, at most m intervals containing p are selected. We give a parameterized algorithm
GREEDYα that belongs to the class of “myopic” algorithms, which are deterministic
algorithms that process the given intervals in order of non-decreasing right endpoint and can …