4
$\begingroup$

I am trying to solve a problem of finding incompatible 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.

Suppose

job  start   end
1    1       3
2    2       11
3    4       6
4    7       8

My required job set J is {2} since all the jobs are incompatible with at least one job of the job set J. I tried to use greedy algorithm like sorting jobs by start time, end time ( adding one and removing all the ones incompatible and so on) But it is not optimal. As you can see in this example. If I add job 1 and then remove all the job incompatible with it, I will remove job 2, Then I will have to add 3 and 4 in the jobset J.

Am I going the right way?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Why have you deleted most of your question? Now it is not clear what you are asking for. $\endgroup$
    – A.Schulz
    May 14, 2013 at 11:59
  • $\begingroup$ @AndrewD Are you around? $\endgroup$
    – user8153
    May 14, 2013 at 14:34

1 Answer 1

Reset to default
1
$\begingroup$

It is clear from your edited post that you will need to use dynamic programming.

Consider solution with the recurrence based on minimum number of time intervals necessary to conflict with all other time intervals, and include a parent pointer so that you can create the set after the algorithm completes.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What if I have a job that has no conflict at all. It will get selected in the initial set. When I take complement then I won't have that job in the complement. So that won't give the right answer $\endgroup$
    – user8153
    May 14, 2013 at 12:33
  • $\begingroup$ All you have to do is create a boolean variable to flag the entries that don't have any conflicts. This can be resolved easily, you are checking for conflicts when using the algorithm anyway. Let me know if this doesn't make sense. $\endgroup$
    – AndrewD
    May 14, 2013 at 12:43
  • $\begingroup$ I think still your solution doesn't satisfy the problem. Suppose I have three jobs, J1 with s1=1 and f1=4, J2 with s2=2 and f2=3, J3 with s3=2 and f3=4. Then it will give me the solution of {J1,J3}. But the required solution is {J2} $\endgroup$
    – user8153
    May 14, 2013 at 12:53
  • $\begingroup$ chat.stackexchange.com/rooms/2710/computer-science $\endgroup$
    – AndrewD
    May 14, 2013 at 13:08
  • $\begingroup$ let us continue this discussion in chat $\endgroup$
    – user8153
    May 14, 2013 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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