###### tags: `ADA 7.2` `Activity Selection` `Interval Scheduling`
# 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
- Input:
- $n$ activities with start times $s_i$ and finish times $f_i$ (the activities are sorted in monotonically increasing order of finish time $f_1 \leq f_2 \leq ... \leq f_n$)
- Output:
- the <span style="background-color:lightyellow">**maximum number**</span> of compatible activities

# Weighted Interval Scheduling Problem

[台大資訊 演算法 | ADA 6.2: Weighted Interval Scheduling 加權區間調度](https://www.youtube.com/watch?v=4NVBJNH1Eu8&list=PLOAQYZPRn2V6ms1JSww6pqXKf5x0o_gan&index=22)
- Input
- $n$ jobs with <$s_i,f_i,v_i$>, <span style="background-color:lightyellow">__$p(j)=$ largest index $i \lt j$__</span> s.t. jobs $i$ and $j$ are compatible
- Output
- the <span style="background-color:lightyellow">**maximum total value**</span> obtainable from compatible
- Subproblems
- $WIS(i)$: weighted interval scheduling for the first $i$ jobs
- Goal: $WIS(n)$
- Dynamic programming algorithm
$$M_i=\begin{cases} 0 & \text {if $i$ = 0} \\ max(v_i + M_{p(i)}, M_{i-1}) & \text{otherwise}\end{cases}$$
- <span style="background-color:lightyellow">__$p(j)=$ largest index $i \lt j$__</span>

# Interval Scheduling Problem - Algorithm

- Input
- $n$ activities with <$s_i,f_i$>, <span style="background-color:lightyellow">__$p(j)=$ largest index $i \lt j$__</span> s.t. jobs $i$ and $j$ are compatible
- Output
- the <span style="background-color:lightyellow">**maximum number**</span> of activities
- Dynamic programming algorithm
$$M_i = \begin{cases} 0 & \text {if $i$ = 0} \\ max(1 + M_{p(i)}, M_{i-1}) & \text{otherwise} \end{cases}$$
- Greedy algorithm
$$M_i = \begin{cases} 0 & \text {if $i$ = 0} \\ 1 + M_{p(i)} & \text{otherwise} \end{cases}$$

# Interval Scheduling Problem - Proof
1. **Optimal Substructure:**

[台大資訊 演算法 | ADA 5.1: Dynamic Programming 動態規劃](https://www.youtube.com/watch?v=x3BCX9hBWZQ&list=PLOAQYZPRn2V6ms1JSww6pqXKf5x0o_gan&index=17&t=26m39s)

2. <span style="background-color:lightyellow">**Greedy-Choice Property:**</span>
- Pre-process: Without loss of generality $s_1 \lt s_2 \lt ... \lt s_n$ and $f_1 \lt f_2 \lt ... \lt f_n$ (大的包小的則不考慮大的 → 用小的取代大的一定不會變差)
- Goal: <span style="background-color:LightYellow">$1 + M_{p(i)} \ge M_{i - 1}$</span>
- Proof
- Assume there is an OPT solution for the first $i - 1$ activities $M_{i - 1}$
- $A_j$ is the last activity in the OPT solution → $M_{i - 1} = 1 + M_{p(j)}$
- Replacing $A_j$ with $A_i$ does not make the OPT worse → <span style="background-color:LightYellow">$1 + M_{p(i)}$ $\ge 1 + M_{p(j)} =$ $M_{i - 1}$</span>

# Exercises

## Interval Scheduling Problem

[435. Non-overlapping Intervals - LeetCode](https://leetcode.com/problems/non-overlapping-intervals/description/)

1. Use a <span style="background-color:lightyellow">**simple rule**</span> <span style="color:RoyalBlue">**(Earliest Finish Time)**</span> to select a request $i$
2. Reject all requests incompatible with $i$
3. Repeat until all requests are processed

class Solution {
    func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
        let n = intervals.count
        let intervals = intervals.sorted { $0[1] < $1[1] }
        var count = 0
        var currEnd = Int.min
        for i in 0..<n where currEnd <= intervals[i][0] {
            count += 1
            currEnd = intervals[i][1]
        }
        return n - count
    }
}

## Weighted Interval Scheduling Problem

[1235. Maximum Profit in Job Scheduling - LeetCode](https://leetcode.com/problems/maximum-profit-in-job-scheduling/)

class Solution {
    func jobScheduling(_ startTime: [Int], _ endTime: [Int], _ profit: [Int]) -> Int {
        let n = startTime.count
        var jobs: [(start: Int, end: Int, profit: Int)] = []
        (0..<n).forEach { jobs.append((startTime[$0], endTime[$0], profit[$0])) }
        jobs.sort { $0.end < $1.end }
        var maxProfit = 0
        var dp: [(end: Int, maxProfit: Int)] = [(-1, 0)]
        for currJob in jobs {
            let i = binarySearch(dp, currJob.start)
            let currProfit = max(maxProfit, dp[i].maxProfit + currJob.profit)
            dp.append((currJob.end, currProfit))
            maxProfit = max(maxProfit, currProfit)
        }
        return maxProfit
    }
    private func binarySearch(_ nums: [(end: Int, maxProfit: Int)], _ target: Int) -> Int {
        let n = nums.count
        var left = 0
        var right = n - 1
        while left < right {
            let mid = left + (right - left + 1) / 2
            if nums[mid].end <= target {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left
    }
}

## Finding the overlap



func isOverlap(_ a: [Int], _ b: [Int]) -> Bool {
    let (start1, end1) = (a[0], a[1])
    let (start2, end2) = (b[0], b[1])
    return min(end1, end2) - max(start1, start2) > 0
}

[223. Rectangle Area - LeetCode](https://leetcode.com/problems/rectangle-area/description/)

class Solution {
    func computeArea(_ ax1: Int, _ ay1: Int, _ ax2: Int, _ ay2: Int, _ bx1: Int, _ by1: Int, _ bx2: Int, _ by2: Int) -> Int {
        let a = (ax2 - ax1) * (ay2 - ay1)
        let b = (bx2 - bx1) * (by2 - by1)
        var overlap = 0
        let w = min(ax2, bx2) - max(ax1, bx1)
        let h = min(ay2, by2) - max(ay1, by1)
        if w > 0 && h > 0 { overlap = w * h }
        return a + b - overlap
    }
}