2
$\begingroup$

This question already has an answer here:

I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.

I have a set of jobs with start and finish time and I want to find the smallest subset of this jobs such that all the jobs are incompatible with at least one job of this subset. And all the jobs in this subset are compatible

Suppose

job  start   end
1    1       3
2    2       11
3    4       6
4    12       14

My required job set J is {2,4} since all the jobs are incompatible with at least one job of the job set J. And all the jobs in the job set J are compatible. I tried using earliest deadline first and schedule but it doesn't work. Any suggestions?

Am I going the right way?

$\endgroup$

marked as duplicate by xskxzr, David Richerby, Apass.Jack, Yuval Filmus algorithms Oct 26 '18 at 20:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

It seems that you are looking for the minimum maximal independent set of an interval graph. A minimum maximal independent set in a graph is the same as a minimum weight independent dominating set, with all vertices weights equal to 1. Since interval graphs are a special case of chordal graphs, Martin Farber's paper Independent domination in chordal graphs (Operational Research Letters, 1(4):134–138, 1982; ACM Digital Library) contains the algorithm you are looking for.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.