ADA 7.2: Activity Selection / Interval Scheduling
Textbook Chapter 16.1 - An activity-selection problem
Chapter 4.1 in Algorithm Design by Kleinberg & Tardos
Interval Scheduling Problem
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- Input:
- activities with start times and finish times (the activities are sorted in monotonically increasing order of finish time )
- Output:
- the maximum number of compatible activities
Weighted Interval Scheduling Problem
台大資訊 演算法 | ADA 6.2: Weighted Interval Scheduling 加權區間調度
- Input
- jobs with <>, largest index s.t. jobs and are compatible
- Output
- the maximum total value obtainable from compatible
- Subproblems
- : weighted interval scheduling for the first jobs
- Goal:
- Dynamic programming algorithm
- largest index
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Interval Scheduling Problem - Algorithm
- Input
- activities with <>, largest index s.t. jobs and are compatible
- Output
- the maximum number of activities
- Dynamic programming algorithm
- Greedy algorithm
Interval Scheduling Problem - Proof
-
Optimal Substructure:
台大資訊 演算法 | ADA 5.1: Dynamic Programming 動態規劃
-
Greedy-Choice Property:
- Pre-process: Without loss of generality and (大的包小的則不考慮大的 → 用小的取代大的一定不會變差)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- Goal:
- Proof
- Assume there is an OPT solution for the first activities
- is the last activity in the OPT solution →
- Replacing with does not make the OPT worse →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Exercises
Interval Scheduling Problem
435. Non-overlapping Intervals - LeetCode
- Use a simple rule (Earliest Finish Time) to select a request
- Reject all requests incompatible with
- Repeat until all requests are processed
Weighted Interval Scheduling Problem
1235. Maximum Profit in Job Scheduling - LeetCode
Finding the overlap
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
223. Rectangle Area - LeetCode