Greedy Algorithms for Interval Scheduling
Lecture 7 Greedy Algorithms
Interval Scheduling
•
There are
n
meeting requests, meeting i takes time
(s
i
, t
i
)
•
Cannot schedule two meeting together if their
intervals overlap.
•
Goal: Schedule as many meetings as possible.
•
Example: Meetings (1,3), (2, 4), (4, 5), (4, 6), (6, 8)
•
Solution: 3 meetings ((1, 3), (4, 5), (6, 8))
Recap: Algorithm
•
Always try to schedule the meeting that
ends earliest
Schedule
1.
Sort the meetings according to end time
2.
For i = 1 to n
3.
If meeting i does not conflict with previous meetings
4.
Schedule meeting i
Proof of correctness in pictures
……
I have scheduled the most
number of possible meetings!
……
I have scheduled the most
number of possible meetings!
……
No you are wrong! There is a
way to schedule more meetings.
……
Can you show me how to do
that? Here are the first two
meetings I scheduled.
……
Yes, those are fine. I made the
same decisions.
i
3
……
and this is my third meeting i
3
.
j
3
……
Wait, you can’t do that. You
need to schedule meeting j
3
i
3
……
My meeting i
3
ends before your
meeting j
3
, so if you swap j
3
to i
3
,
you are still OK right?
j
3
……
I guess you are right. Fine I will
do that.
i
3
……
But isn’t this the same thing?
You could have swapped to my
5
th
meeting.
……
OK you got me on the 3
rd
meeting. But you made another
mistake on the 5
th
meeting!
May rounds later……
……
……
OK, OK, you can keep all of your
meetings, but I could still
schedule a meeting j
k+1
!
……
……
That doesn’t make any sense. If
there is such a meeting, I must
consider it after i
k
, and I would
have scheduled that meeting!
OK, you win.
The Encoding Problem (Hoffman Tree)
•
Problem: Given a long string with
n
different
characters in alphabet, find a way to encode these
characters into binary codes that minimizes the
length.
•
Example: “
a
a
b
a
b
c”, n = 3, alphabet = {a,b,c}•
If a = ‘0’, b = ’11’, c = ‘10’, then the string can be
encoded as ‘
0
0
11
0
11
10’.
Why don’t just use ASCII?
•
Different letters appear
with very different
frequency.
•
Using an encoding of
varying length can save
space.
•
Now of course
memory/disk are
cheap, but some
communications can
be expensive.
What kind of encodings are allowed?
•
Bad example: If a = ‘0’, b = ’01’, c = ‘1’
•
Given encoding
00010011
, it can be
‘aababc’, but can also be ‘aaacabc’ (and others)
•
Want an encoding that allow
unique
decoding.
•
Sufficient condition: Prefix free encoding
•
Definition:
No code should be a
prefix
of another code.
•
(In previous example, encoding of
a
is a
prefix
for
encoding of
b
.)
Prefix-free encoding vs. Trees
a
b
c
d
0
0
0
1
1
1
1
a = 00
b = 01
c = 110
d = 111
Character = Leaves of the Tree
Encoding = Path from root to the character
Prefix free = no characters for intermediate nodes
Cost of the Tree
a
b
c
d
0
0
0
1
1
1
1
5
10
3
6
Cost = sum of Frequency * Depth
= 5*2 + 10*2 + 3*3 + 6*3
= 57
Hoffman Tree problem
•
Given a long string with
n
different characters in
alphabet, find a way to encode these characters
into binary codes that minimizes the length.
•
Given an alphabet of
n
characters, character
i
appears
w
i
times, find an encoding tree with
minimum cost.
Algorithm
Hoffman Tree
1.
REPEAT
2.
Select two characters with smallest frequencies
3.
Merge them into a new character, whose frequency is the sum
4.
UNTIL there is only one character
Proof Sketch
•
Use induction: Assume algorithm finds the optimal
solution for alphabet of size
n
, we want to prove
that it works for alphabet of size
n+1
.
•
Base Case: n = 1 is trivial. (cost = 0 in this case)
Induction Step
i
j
First merged
i, j
(characters with lowest frequency)
i
j
i, j
may be in different branches
Goal: Convince OPT that it is OK to merge
i, j
first.
Induction Step
i
j
j
i
After ALG and OPT both merged
i, j
, it reduces to a problem of size
n
!
Induction hypothesis
ALG is optimal, OPT cannot be better.
Interval scheduling with greedy algorithms. Explore how to maximize meeting schedules by sorting and selecting meetings based on ending times. Proof of correctness and optimizing meeting selections illustrated.
Uploaded on Mar 04, 2025 | 1 Views
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Interval Scheduling There are n meeting requests, meeting i takes time (si, ti) Cannot schedule two meeting together if their intervals overlap. Goal: Schedule as many meetings as possible. Example: Meetings (1,3), (2, 4), (4, 5), (4, 6), (6, 8) Solution: 3 meetings ((1, 3), (4, 5), (6, 8))
Recap: Algorithm Always try to schedule the meeting that ends earliest Schedule 1. Sort the meetings according to end time 2. For i = 1 to n 3. If meeting i does not conflict with previous meetings 4. Schedule meeting i
Proof of correctness in pictures I have scheduled the most number of possible meetings!
I have scheduled the most number of possible meetings! No you are wrong! There is a way to schedule more meetings.
Can you show me how to do that? Here are the first two meetings I scheduled. Yes, those are fine. I made the same decisions.
and this is my third meeting i3. i3 j3 Wait, you can t do that. You need to schedule meeting j3
My meeting i3 ends before your meeting j3, so if you swap j3 to i3, you are still OK right? i3 j3 i3 I guess you are right. Fine I will do that.
But isnt this the same thing? You could have swapped to my 5th meeting. OK you got me on the 3rd meeting. But you made another mistake on the 5th meeting!
OK, OK, you can keep all of your meetings, but I could still schedule a meeting jk+1!
That doesnt make any sense. If there is such a meeting, I must consider it after ik, and I would have scheduled that meeting! OK, you win.
The Encoding Problem (Hoffman Tree) Problem: Given a long string with n different characters in alphabet, find a way to encode these characters into binary codes that minimizes the length. Example: aababc , n = 3, alphabet = {a,b,c} If a = 0 , b = 11 , c = 10 , then the string can be encoded as 001101110 .
Why dont just use ASCII? Different letters appear with very different frequency. Using an encoding of varying length can save space. Now of course memory/disk are cheap, but some communications can be expensive.
What kind of encodings are allowed? Bad example: If a = 0 , b = 01 , c = 1 Given encoding 00010011, it can be aababc , but can also be aaacabc (and others) Want an encoding that allow unique decoding. Sufficient condition: Prefix free encoding Definition: No code should be a prefix of another code. (In previous example, encoding of a is a prefix for encoding of b.)
Prefix-free encoding vs. Trees 0 1 a = 00 b = 01 c = 110 d = 111 1 0 1 a b 0 1 c d Character = Leaves of the Tree Encoding = Path from root to the character Prefix free = no characters for intermediate nodes
Cost of the Tree Cost = sum of Frequency * Depth = 5*2 + 10*2 + 3*3 + 6*3 = 57 0 1 1 0 1 a b 0 1 5 10 c d 3 6
Hoffman Tree problem Given a long string with n different characters in alphabet, find a way to encode these characters into binary codes that minimizes the length. Given an alphabet of n characters, character i appears wi times, find an encoding tree with minimum cost.
Algorithm Hoffman Tree 1. REPEAT 2. Select two characters with smallest frequencies 3. Merge them into a new character, whose frequency is the sum 4. UNTIL there is only one character abcd 24 acd 14 ac 8 a b c d 6 3 5 10
Proof Sketch Use induction: Assume algorithm finds the optimal solution for alphabet of size n, we want to prove that it works for alphabet of size n+1. Base Case: n = 1 is trivial. (cost = 0 in this case)
Induction Step i j i j First merged i, j i, j may be in different branches (characters with lowest frequency) Goal: Convince OPT that it is OK to merge i, j first.
Induction Step j i j i After ALG and OPT both merged i, j, it reduces to a problem of size n! Induction hypothesis ALG is optimal, OPT cannot be better.
