Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Stack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack InternalIt is clear from your edited post that you will need to use dynamic programming. A greedy algorithm will not produce an optimal
Consider solution allwith 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.
It is clear from your edited post that you will need to use dynamic programming. A greedy algorithm will not produce an optimal solution all the time.
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.
It is clear from your edited post that you will need to use dynamic programming. A greedy algorithm will not produce an optimal solution all the time.
-------------------------------------No Longer Relevant Answer Below ----------------
Have you tried taking the complement of the set achieved from the Earliest Deadline First Algorithm?
This greedy approach works by selecting the job with the earliest deadline, then checking to see if there are any conflicts with its scheduling (thus accepting the job if there are no conflicts and rejecting if there are). So, the complement of this set should give you what you are looking for (given that there are conflicts that exist with every interval) [and the wikipedia page shows how it is optimal].
See also: Interval Scheduling
To solve your issue with non-conflicting intervals. You can associate a boolean variable with each interval (using an array or built it into the "interval" data structure) that is initially false until there is a compare / found conflict. When there is a conflict found then change it to true. This way all intervals that had no conflicts will have a false variable associated with them and can be added to the complement in linear time. This is a very small addition to the algorithm described above.
It is clear from your edited post that you will need to use dynamic programming. A greedy algorithm will not produce an optimal solution all the time.
-------------------------------------No Longer Relevant Answer Below ----------------
Have you tried taking the complement of the set achieved from the Earliest Deadline First Algorithm?
This greedy approach works by selecting the job with the earliest deadline, then checking to see if there are any conflicts with its scheduling (thus accepting the job if there are no conflicts and rejecting if there are). So, the complement of this set should give you what you are looking for (given that there are conflicts that exist with every interval) [and the wikipedia page shows how it is optimal].
See also: Interval Scheduling
To solve your issue with non-conflicting intervals. You can associate a boolean variable with each interval (using an array or built it into the "interval" data structure) that is initially false until there is a compare / found conflict. When there is a conflict found then change it to true. This way all intervals that had no conflicts will have a false variable associated with them and can be added to the complement in linear time. This is a very small addition to the algorithm described above.
It is clear from your edited post that you will need to use dynamic programming. A greedy algorithm will not produce an optimal solution all the time.
It is clear from your edited post that you will need to use dynamic programming. A greedy algorithm will not produce an optimal solution all the time.
-------------------------------------No Longer Relevant Answer Below ----------------
Have you tried taking the complement of the set achieved from the Earliest Deadline First Algorithm?
This greedy approach works by selecting the job with the earliest deadline, then checking to see if there are any conflicts with its scheduling (thus accepting the job if there are no conflicts and rejecting if there are). So, the complement of this set should give you what you are looking for (given that there are conflicts that exist with every interval) [and the wikipedia page shows how it is optimal].
See also: Interval Scheduling
To solve your issue with non-conflicting intervals. You can associate a boolean variable with each interval (using an array or built it into the "interval" data structure) that is initially false until there is a compare / found conflict. When there is a conflict found then change it to true. This way all intervals that had no conflicts will have a false variable associated with them and can be added to the complement in linear time. This is a very small addition to the algorithm described above.
Have you tried taking the complement of the set achieved from the Earliest Deadline First Algorithm?
This greedy approach works by selecting the job with the earliest deadline, then checking to see if there are any conflicts with its scheduling (thus accepting the job if there are no conflicts and rejecting if there are). So, the complement of this set should give you what you are looking for (given that there are conflicts that exist with every interval) [and the wikipedia page shows how it is optimal].
See also: Interval Scheduling
To solve your issue with non-conflicting intervals. You can associate a boolean variable with each interval (using an array or built it into the "interval" data structure) that is initially false until there is a compare / found conflict. When there is a conflict found then change it to true. This way all intervals that had no conflicts will have a false variable associated with them and can be added to the complement in linear time. This is a very small addition to the algorithm described above.
It is clear from your edited post that you will need to use dynamic programming. A greedy algorithm will not produce an optimal solution all the time.
-------------------------------------No Longer Relevant Answer Below ----------------
Have you tried taking the complement of the set achieved from the Earliest Deadline First Algorithm?
This greedy approach works by selecting the job with the earliest deadline, then checking to see if there are any conflicts with its scheduling (thus accepting the job if there are no conflicts and rejecting if there are). So, the complement of this set should give you what you are looking for (given that there are conflicts that exist with every interval) [and the wikipedia page shows how it is optimal].
See also: Interval Scheduling
To solve your issue with non-conflicting intervals. You can associate a boolean variable with each interval (using an array or built it into the "interval" data structure) that is initially false until there is a compare / found conflict. When there is a conflict found then change it to true. This way all intervals that had no conflicts will have a false variable associated with them and can be added to the complement in linear time. This is a very small addition to the algorithm described above.
