2
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.