Interval
Scheduling
By:
Abhishek Arora
Disclaimer:
All characters
appearing in this article are fictitious. Any resemblance to real
persons, living or dead, is purely coincidental.
Abstract:
A long time ago,
there was a saint born on this earth. Lord Shiva gifted him with
enormous powers in return of his prayers.
One day on seeing the grieving family members of a dead person, the saint got very angry with the death. He couldn’t able to bear the pain and sorrow caused by death. He made a protective layer on the earth by his powers so that no death reapers can now enter the earth and take a life.
One day on seeing the grieving family members of a dead person, the saint got very angry with the death. He couldn’t able to bear the pain and sorrow caused by death. He made a protective layer on the earth by his powers so that no death reapers can now enter the earth and take a life.
This caused a great
imbalance in the functioning of earth and all the gods became very
tensed especially Yamraj because it was their duty to make proper
balance of life and death on this earth. All the gods gathered
together and request the saint to remove that protected layer but he
didn't agree with them. Though he allowed Yamraj to send his one
death reaper on the night of Full moon to take life and carry souls
to afterlife one by one.
It was a very
short period of time to carry all the souls to afterlife. Yamraj was
in the state of dilemma to how to properly schedule his time and
carry maximum souls to afterlife because he can only send one
death reaper to earth and the death time of every earthling is
written in his life book. Time to take a soul depends upon how far
is the death place of the person from the place of Yamraj. Reapers
carry soul to Yamraj one by one.
He didn't have a
solution for this question. Goddess Saraswati is the goddess of
knowledge. Yamraj was sure that goddess Saraswati must have a
solution for his problem. Yamraj decided to take help from Goddess
Saraswati.
Goddess Saraswati
being the goddess of knowledge knew how to handle such type of
problem. She picked a stone and wrote the procedure on it. She told
the Yamraj that this procedure would be known as Interval Scheduling
in the future.
Interval
Scheduling
Given a set of tasks
with their arrival time and running time we need to schedule them
within a given time period such that we are able to schedule maximum
number of tasks.
Let p1,p2,p3....pI
be the tasks to be scheduled.
Let s1,s2,s3......sI
be the starting time of tasks.
Let
r1,r2,r3.......rI be the time required by each task respectively.
Algorithm:
Implementation:
• Sorting
intervals according to the right-most ends (their finishing time)
• For every
consecutive task:
- If the left-most end(starting time) is after the right-most end of the last
selected
interval then we select this interval
- Otherwise we skip it and go to the next interval
This
approach is a Greedy approach.
Consider
the following set of activities represented graphically in
non-decreasing order of finishing times
Using
the greedy strategy an optimal solution is {1, 4, 8, 11}.
Scenario
of Yamraj:
But
Yamraj wasn't able to understand a single word written above.
Then
Goddess Saraswati smiled and said to Yamraj:
- Taking a soul to afterlife is a task for you.
- Death time of a person is the starting time of your task.
- Time to reach to the dying person and taking his soul to your place is the time required to complete that task.
This approach worked
for Yamraj and he implemented this approach in bringing souls to
afterlife on every Full moon night for many years.
But as the years
passed Yamraj noticed that sin and violence had increased a lot in
the earth. But he couldn't able to do anything. He just have one
night to cause deaths in the earth and it also didn't assure that
Yamraj is picking bad guys.
It made Yamraj to
worry. He wanted to do something about the increasing sin and
“adharm” on earth. But he didn't know how to pick maximum bad
guys in his given time slot. So he again decided to take help from
Goddess Saraswati. He went to Goddess Saraswati and asked for her
help.
Goddess Saraswati
smiled and asked Yamraj, “how will you decide who is bad and who is
good??”.
Yamraj answered,
“Devi we keep a count of all the deeds of humans. If a human do
sins throughout his life he gets punished in the afterlife.”
Goddess Saraswati
smiled and said to Yamraj, “ I can help you with this but it
doesn't guarantee you that you will able to bring maximum souls to
afterlife”
It put Yamraj in a
thinking state. He didn't know what to do now. He want to take as
many as possible lives on every full moon night but he also want to
do something about the increasing sins and adharma on earth. So
Yamraj said, “I want you to tell me the way to pick as many as
possible bad guys.”
Goddess Saraswati
again picked a stone and wrote the procedure on it. She told the
Yamraj that this procedure would be known as Dynamic Weighted
Interval Scheduling in the future.
Weighted
Interval Scheduling
Suppose we are given
n jobs. Each job i has a start time si , a finish time fi , and a
weight wi .
We would like to
find a set M of optimal jobs whose total weight is maximized.
Let us assume that
our n jobs are sorted by non-decreasing finish times fi .
M(i)= The maximum
weight of any set of compatible jobs, all of which finish by fi .
p(j)= job with the
largest index less than j which is compatible with job j. In other
words, the largest k such that fk ≤ sj . If no such job exists
define p(j) = 0.
Then
M(i) = max{M(i −
1), wi + M(p(i))}.
Consider the optimal
solution for M(i). Either job i is used or it is not.
- If it is not, then we have a maximum weight set of compatible jobs from among jobs 1 through i − 1. By definition, this is M(i − 1).
- Alternatively, if i is used for M(i). Since jobs p(i) + 1 through i − 1 all conflict with job i, this means that the remaining jobs selected for M(i) are drawn from 1 through p(i). Removing i from the optimal solution for M(i) yields a compatible solution on jobs 1 . . . p(i).
Therefore M(i) =
wi + M(p(i)).
Finally, since M(i)
is a maximization, the larger of these two terms is correct.
As base cases, we
define M(0) = 0 and M(1) = w1.
The algorithm works
as follows:
- sort jobs by increasing finish times.
- compute function p(i) for i from 1 to n (this can clearly be done in O(n2) time. If we want to do better, we can either binary search for each i, or all p(i) values can be computed in a single linear pass if we have already created a second list of jobs sorted by increasing start times).
set M(0) = 0 and
M(1) = w1
loop over i from 2
to n
set M(i) = max{M(i
− 1), wi + M(p(i))}
endloop
Sorting takes O(n
log n) time. The computation of p(i) takes another O(n log n) time
and the main loop are both linear, and therefore the total running
time is O(n log n).
Note that we
computed the value of an optimal schedule, but not the schedule
itself. To actually compute the actual schedule, we have a few
options. One is to use the computed values M(i) to reverse engineer
an optinal set A of jobs to select.
Alternatively, we
can change the algorithms so we build lists as we go:
- sort jobs by increasing finish times.
- compute function p(i) for i from 1 to n
set M(0) = 0 and
M(1) = w1
set A(0) = 0 and
A(1) = {1}
loop over i from 2
to n
if M(i − 1) >
wi + M(p(i))
set A(i) = A(i −
1) and M(i) = M(i − 1)
else M(i − 1) ≤
wi + M(p(i))
set A(i) = {i} ∪
A(p(i)) and M(i) = wi + M(p(i))
endif
endloop
Again Yamraj wasn't
able to understand how to implement it. Then goddess Saraswati told
him:
- Taking a soul to afterlife is a job for you
- Death time of a person is the starting time of your task.
- Time to reach to the dying person and taking his soul to your place is the time required to complete that job.
- All the bad deeds done by that human is the weight of the job.
Yamraj was finally
happy to have a solution for this. He continued to use this approach
to take life of bad guys until the death protecting layer of earth
was removed by the saint.
In the final moments
of the saint’s life when he was old and in the state of misery, and
no one was there to support him. He was waiting eagerly for his death
but death wasn’t able to come to him due to his protected layer. He
then realized that it is very important to leave this life and move
to afterlife. He removed that protected layer and apologize to all
the gods. It was a sigh of relief for all the gods specially Yamraj.
References:
faculty.cse.tamu.edu/nikolova/Teaching/.../lec3.pdf - United
States
lonati.di.unimi.it/algo/0910/lab/kowalski6.pdf
