Try   HackMD
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

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:
    • n
      activities with start times
      si
      and finish times
      fi
      (the activities are sorted in monotonically increasing order of finish time
      f1f2...fn
      )
  • Output:
    • the maximum number of compatible activities

Weighted Interval Scheduling Problem

台大資訊 演算法 | ADA 6.2: Weighted Interval Scheduling 加權區間調度

  • Input
    • n
      jobs with <
      si,fi,vi
      >,
      p(j)=
      largest index
      i<j
      s.t. jobs
      i
      and
      j
      are compatible
  • Output
    • the maximum total value obtainable from compatible
  • Subproblems
    • WIS(i)
      : weighted interval scheduling for the first
      i
      jobs
    • Goal:
      WIS(n)
  • Dynamic programming algorithm
    Mi={0if i = 0max(vi+Mp(i),Mi1)otherwise
  • p(j)=
    largest index
    i<j

    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
    • n
      activities with <
      si,fi
      >,
      p(j)=
      largest index
      i<j
      s.t. jobs
      i
      and
      j
      are compatible
  • Output
    • the maximum number of activities
  • Dynamic programming algorithm
    Mi={0if i = 0max(1+Mp(i),Mi1)otherwise
  • Greedy algorithm
    Mi={0if i = 01+Mp(i)otherwise

Interval Scheduling Problem - Proof

  1. Optimal Substructure:

    台大資訊 演算法 | ADA 5.1: Dynamic Programming 動態規劃

  2. Greedy-Choice Property:

  • Pre-process: Without loss of generality
    s1<s2<...<sn
    and
    f1<f2<...<fn
    (大的包小的則不考慮大的 → 用小的取代大的一定不會變差)
    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:
    1+Mp(i)Mi1
  • Proof
    • Assume there is an OPT solution for the first
      i1
      activities
      Mi1
    • Aj
      is the last activity in the OPT solution →
      Mi1=1+Mp(j)
    • Replacing
      Aj
      with
      Ai
      does not make the OPT worse →
      1+Mp(i)
      1+Mp(j)=
      Mi1

      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

  1. Use a simple rule (Earliest Finish Time) 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

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

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 →

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

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 } }