# Greedy Algorithm
## ‣ Interval Scheduling
Given many small intervals and a bigger interval. To fit the most smaller intervals possible into the bigger intervals.
* [ ] ~~Consider jobs in ascending order of starting time.~~
The longger: A = {10, 20}
The shorter: {a : {10, 20}, b : {11,12}, c : {13,14}}
Expect: {a : {11,12}, c : {13,14}}
Because a and c are not in confict
Algorithm Output:
1. Sort by the processing time:
{a : {10, 20}, b : {11,12}, c : {13,14}}
2. Consider these sorted intervals one by one
{a: {10, 20}} takes the whole duration of A
so output a
3. Output != Expect
4. Greedy algorithm by ascending order of starting time not working
* [ ] ~~Consider jobs in ascending order of duration.~~
The longger: A = {10, 20}
The shorter: {a : {10, 14}, b : {13, 15}, c : {14, 20}}
The duration: {a : 4, b : 2, c : 6}
Expect: {a : {10,14}, c : {14,20}}
Because a and c are not in confict
Algorithm Output:
1. Sort by duration:
{b : {13, 15}, a : {10, 14}, c : {14, 20}}
2. Consider these sorted intervals one by one
{b: {13, 15}} will be scheduled and all the other two have conflicts
so output b
3. Output != Expect
4. Greedy algorithm by ascending order of duration not working
* [x] Consider jobs in ascending order of ending time.
## ‣ Interval Partitioning
Given many small intervals and some classrooms. To fit all smaller intervals into the classrooms without conflicts such that the number of classrooms should be the minimum possible.
* [x] Consider jobs in ascending order of starting time.
* [ ] ~~Consider jobs in ascending order of duration.~~
The shorter: {a : {10, 14}, b : {14, 16}, c : {19, 20}}
The duration: {a : 4, b : 2, c : 1}
Expect: 1, {a : {10, 14}, b : {14, 16}, c : {19, 20}}
Because they are all compatible
Algorithm Output:
1. Sort by duration:
{c : {19, 20}, b : {14, 16}, a : {10, 14}}
2. Consider these sorted intervals one by one
1, {c : {19, 20}}
2, {b : {14, 16}}
3, {a : {10, 14}}
Three classroom will be scheduled
3. Output != Expect
4. Greedy algorithm by ascending order of duration not working
* [ ] ~~Consider jobs in ascending order of finish time.~~
The shorter: {a:{10, 12}, b:{10, 14}, c:{13, 20}, d: {15, 19}}
Expect: 1, {a : {10,12}, c : {13,20}}
2, {b : {10,14}, d : {15,19}}
So 2 classrooms should be scheduled
Algorithm Output:
1. Sort by finish time:
{a:{10, 12}, b:{10, 14}, d: {15, 19}, c:{13, 20}}
2. Consider these sorted intervals one by one
1, {a:{10, 12}, d: {15, 19}}
2, {b:{10, 14}, }
3, {c:{13, 20}}
Three classroom will be scheduled
3. Output != Expect
4. Greedy algorithm by ascending order of finish time not working
## ‣ Scheduling to minimize lateness
Given many small intervals and some classrooms. To fit all smaller intervals into the classrooms without conflicts such that the number of classrooms should be the minimum possible.
* [ ] ~~Consider jobs in ascending order of processing time.~~
job: 1 2
t: 1 10
d: 20 10
Expect: {job2, job1}
{0-10, 10-11}
lateness:{ 0, 0 }
Max : 0
Algorithm Output:
1. Sort by the processing time:
{job1, job2}
2. Consider these sorted intervals one by one
{0-1, 1-11}
lateness:{ 0, 1 }
Max : 1
Output : 1
3. Output != Expect
4. Greedy algorithm by ascending order of duration not working
* [ ] ~~Consider jobs in ascending order of slackness by~~ $$d\_j - t\_j$$~~.~~
job: 1 2
t: 1 10
d: 3 10
Expect: {job1, job2}
{0-1, 1-11}
lateness:{ 0, 1 }
Max : 1
Algorithm Output:
1. Sort by the slackness:
{job2(0), job1(2)}
10 - 10 , 3 - 1
2. Consider these sorted intervals one by one
{0 - 10, 10-11}
lateness:{ 0, 8 (11 - 3) }
Max : 8
Output : 8
3. Output != Expect
4. Greedy algorithm by ascending order of slackness not working
* [x] Consider jobs in ascending order of finish time.
## ‣Overview
