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?
-
1$\begingroup$ Why have you deleted most of your question? Now it is not clear what you are asking for. $\endgroup$A.Schulz– A.Schulz2013年05月14日 11:59:13 +00:00Commented May 14, 2013 at 11:59
-
$\begingroup$ @AndrewD Are you around? $\endgroup$user8153– user81532013年05月14日 14:34:25 +00:00Commented May 14, 2013 at 14:34
1 Answer 1
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.
-
$\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– user81532013年05月14日 12:33:18 +00:00Commented 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– AndrewD2013年05月14日 12:43:35 +00:00Commented 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– user81532013年05月14日 12:53:38 +00:00Commented May 14, 2013 at 12:53
-
$\begingroup$ chat.stackexchange.com/rooms/2710/computer-science $\endgroup$AndrewD– AndrewD2013年05月14日 13:08:10 +00:00Commented May 14, 2013 at 13:08
-
$\begingroup$ let us continue this discussion in chat $\endgroup$user8153– user81532013年05月14日 13:19:59 +00:00Commented May 14, 2013 at 13:19
Explore related questions
See similar questions with these tags.