Issues with using greedy algorithm (Interval scheduling variant) 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?
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.