search

JangoBoogaloo / LeetCodeExcercise

1 stars 0 forks source link

Max Profit Schedule Question #335

Open JangoBoogaloo opened 2 weeks ago

JangoBoogaloo commented 2 weeks ago

Description

Tasks have (start, end) time with profit. Try to schedule to get maximum profit.

Condition

Can not concurrent tasks or can have at most x concurrent tasks

DP Idea

  1. Sort data by start time
  2. Reverse order DP, because the last element start time don't need to worry about conflict with it's next element
  3. Consider elements start at time i, get maximum profits for combinations start at i
  4. Save that maximum profits in DP.
  5. Finally get DP for starting at beginning i
JangoBoogaloo commented 2 weeks ago

Potential Related Question

Maximum Length of Pair Chain

Longest Increasing Subsequence

Maximum Earnings From Taxi

Two Best Non-Overlapping Events

JangoBoogaloo commented 2 weeks ago

Follow Up

How is it different from SweepLine