I'm looking for an algorithm to solve the following variant of interval programming: schedule some tasks on several machines, which are only available during a certain time interval. Two tasks can not be performed at the same time by the same machine. I am trying to maximize the number of scheduled tasks.
I thought about the greedy algorithm that consists of first programming the task that ends as soon as possible, in the compatible machine whose last task ends as last (we consider that each machine has at the beginning a task that ends at the beginning of its working interval). However, this idea does not work, how can we see considering the instance of the problem where we have two machines, working in the intervals (0, 3) and (1, 4), with the tasks (1, 3) and (2, 4)? ).
However, this way of selecting the machine in which we program the task is not so stupid and avoids other problems (the algorithm works if we are allowed to exchange the end of the working interval of the machines).
Is there a quick algorithm to solve this or is it a difficult problem?