Greedy Algorithms in Interval Scheduling
Lecture 15
CSE 331
Few points…
•
Project group signups
–
Your UBIT ID is XXX if XXX@buffalo.edu is the email ID
•
Please don’t enter your person number!
•
HWs
–
Cite your sources
–
Answers should be self-contained
–
Separate out proof idea and proof details
•
Summary in idea and detailed proof in details.
–
Upload a legible PDF file. If Autograder can’t open it, we can’t grade it.
–
Please don’t cheat!
•
Recitations in week 6 and 7
–
Week 6: TAs will briefly go over the sample midterm, suggest
studying tips, etc.
–
Week 7: (this is the midterm week!) Q/A with the TAs.
Project groups due
TODAY!
D
e
a
d
l
i
n
e
:
F
r
i
d
a
y
,
M
a
r
c
h
4
,
1
1
:
5
9
p
m
Greedy algorithms
Build the final solution piece by piece
Never undo a decision
Know when you see it
End of Semester blues
Project
331 homework
331 HW
Exam study
Party!
Write up a term paper
Can only do one thing at any day: what is the
maximum number of tasks that you can do?
The optimal solution
331 HW
Exam study
Party!
Can only do one thing at any day: what is the
maximum number of tasks that you can do?
Interval Scheduling Problem
I
n
p
u
t
:
n
i
n
t
e
r
v
a
l
s
[
s
(
i
)
,
f
(
i
)
)
f
o
r
1
≤
i
≤
n
{ s(i), … ,f(i)-1 }Algorithm with examples
Interval Scheduling Problem
•
Input
: n intervals; ith interval: [s(i), f(i)).
•
Output
: A valid schedule with maximum number of intervals in
it (over all valid schedules).
•
Def
: A schedule S
⊆
[n] ([n] = {1, 2, …, n})•
Def
: A valid schedule S has no
conflicts
.
•
Def
: intervals i and j conflict if they overlap.
Interval Scheduling Problem
i
j
i
j
Conflicts:
No conflicts:
Example 1
No intervals overlap
Algorithm?
No intervals overlap
R
: set of requests
Example 2
At most one overlap/task
Algorithm?
At most one overlap
R
: set of requests
Set
S
to be the empty set
While
R
is not empty
Choose
i
in
R
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
Remove
i
from
R
Example 3
Set
S
to be the empty set
While
R
is not empty
Choose
i
in
R
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
More than one conflict
Greedily solve your blues!
Project
331 HW
Exam study
Party!
Write up a term paper
Arrange tasks in some order and iteratively pick non-
overlapping tasks
Making it more formal
Set
S
to be the empty set
While
R
is not empty
Choose
i
in
R
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
More than one conflict
Associate a
value
v(i)
with task
i
Choose
i
in
R
that minimizes
v(i)
What is a good choice for v(i)?
Set
S
to be the empty set
While
R
is not empty
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
More than one conflict
Associate a
value
v(i)
with task
i
Choose
i
in
R
that minimizes
v(i)
v(i)
=
f(i)
–
s(i)
Set
S
to be the empty set
While
R
is not empty
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
Smallest duration first
Choose
i
in
R
that minimizes
f(i) – s(i)
v(i)
=
s(i)
Set
S
to be the empty set
While
R
is not empty
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
Earliest time first?
Choose
i
in
R
that minimizes
s(i)
So are we
done?
Not so fast….
Set
S
to be the empty set
While
R
is not empty
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
Earliest time first?
Choose
i
in
R
that minimizes
s(i)
Pick job with minimum conflicts
Set
S
to be the empty set
While
R
is not empty
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
Choose
i
in
R
that has smallest number of conflicts
So are we
done?
Nope (but harder to show)
Set
S
to be the empty set
While
R
is not empty
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
Choose
i
in
R
that has smallest number of conflicts
Set
S
to be the empty set
While
R
is not empty
Add
i
to
S
Remove all tasks that conflict with
i
from
R
Return
S
*
= S
Choose
i
in
R
that has smallest number of conflicts
Interval Scheduling is a classic algorithmic problem where the goal is to schedule a set of tasks to maximize efficiency without overlap. Greedy algorithms play a crucial role in solving this problem by making locally optimal choices at each step. The concept of greediness, building the solution step by step, and never undoing a decision are key aspects of this approach. In this context, the Interval Scheduling Problem is explained along with conflicts, valid schedules, and examples. The end-of-semester scenario highlights the importance of task prioritization and optimal planning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 15 CSE 331
Few points Project group signups Your UBIT ID is XXX if XXX@buffalo.edu is the email ID Please don t enter your person number! HWs Cite your sources Answers should be self-contained Separate out proof idea and proof details Summary in idea and detailed proof in details. Upload a legible PDF file. If Autograder can t open it, we can t grade it. Please don t cheat! Recitations in week 6 and 7 Week 6: TAs will briefly go over the sample midterm, suggest studying tips, etc. Week 7: (this is the midterm week!) Q/A with the TAs.
Project groups due TODAY! Deadline: Friday, March 4, 11:59pm
Greedy algorithms Build the final solution piece by piece Being short sighted on each piece Never undo a decision Know when you see it
End of Semester blues Can only do one thing at any day: what is the maximum number of tasks that you can do? Write up a term paper Party! Exam study 331 homework 331 HW Project Saturday Sunday Monday Tuesday Wednesday
The optimal solution Can only do one thing at any day: what is the maximum number of tasks that you can do? Party! Exam study 331 HW Saturday Sunday Monday Tuesday Wednesday
Interval Scheduling Problem Input: n intervals [s(i), f(i)) for 1 i n { s(i), ,f(i)-1 } Output: A schedule S of the n intervals No two intervals in S conflict |S| is maximized
Interval Scheduling Problem Input: n intervals; ith interval: [s(i), f(i)). Output: A valid schedule with maximum number of intervals in it (over all valid schedules). Def: A schedule S [n] ([n] = {1, 2, , n}) Def: A valid schedule S has no conflicts. Def: intervals i and j conflict if they overlap.
Interval Scheduling Problem Conflicts: i j No conflicts: i j
Example 1 No intervals overlap
Algorithm? No intervals overlap R: set of requests Set S to be the empty set While R is not empty Choose i in R Add i to S Remove i from R Return S*= S
Example 2 At most one overlap/task
Algorithm? At most one overlap R: set of requests Set S to be the empty set While R is not empty Choose i in R Add i to S Remove all tasks that conflict with i from R Remove i from R Return S*= S
Example 3 Task 5 Task 4 More than one conflict Task 3 Task 2 Task 1 Set S to be the empty set While R is not empty Choose i in R Add i to S Remove all tasks that conflict with i from R Return S*= S
Greedily solve your blues! Arrange tasks in some order and iteratively pick non- overlapping tasks Write up a term paper Party! Exam study 331 HW Project Saturday Sunday Monday Tuesday Wednesday
Making it more formal Task 5 Task 4 More than one conflict Task 3 Task 2 Task 1 Set S to be the empty set While R is not empty Associate a value v(i) with task i Choose i in R Add i to S Choose i in R that minimizes v(i) Remove all tasks that conflict with i from R Return S*= S
What is a good choice for v(i)? Task 5 Task 4 More than one conflict Task 3 Task 2 Task 1 Set S to be the empty set While R is not empty Associate a value v(i) with task i Choose i in R that minimizes v(i) Add i to S Remove all tasks that conflict with i from R Return S*= S
v(i) = f(i) s(i) Task 5 Task 4 Smallest duration first Task 3 Task 2 Task 1 Set S to be the empty set While R is not empty Choose i in R that minimizes f(i) s(i) Add i to S Remove all tasks that conflict with i from R Return S*= S
v(i) = s(i) Task 5 Task 4 Earliest time first? Task 3 Task 2 Task 1 Set S to be the empty set So are we done? While R is not empty Choose i in R that minimizes s(i) Add i to S Remove all tasks that conflict with i from R Return S*= S
Not so fast. Task 5 Task 4 Earliest time first? Task 3 Task 2 Task 1 Task 6 Set S to be the empty set While R is not empty Choose i in R that minimizes s(i) Add i to S Remove all tasks that conflict with i from R Return S*= S
Pick job with minimum conflicts Task 5 Task 4 Task 3 Task 2 Task 1 Task 6 Set S to be the empty set While R is not empty So are we done? Choose i in R that has smallest number of conflicts Add i to S Remove all tasks that conflict with i from R Return S*= S
Nope (but harder to show) Set S to be the empty set While R is not empty Choose i in R that has smallest number of conflicts Add i to S Remove all tasks that conflict with i from R Return S*= S
Task 7 Task 5 Task 4 Task 17 Task 18 Task 3 Task 2 Task 15 Task 16 Task 1 Task 12 Task 14 Task 13 Task 10 Task 11 Task 9 Task 8 Task 6 Set S to be the empty set While R is not empty Choose i in R that has smallest number of conflicts Add i to S Remove all tasks that conflict with i from R Return S*= S
