Greedy Algorithms

Question 1

Coin Selection
Select K coins to maximize the total profit. There is one rule: you can select ci2 only if ci1 is selected

Answer 1

Greedy solution Θ(nlogn)
* if Ci1 >= Ci2, consider two items with value Ci1 and Ci2 and weight 1
* otherwise, consider just one item with value Ci1 + Ci2 and weight 2

Then use greedy solution for the fractional knapsack problem. But the very last step is different because we have 2 cases for residual capacity:
* residual capacity is 2, next item has weight 2. Optimal solution
* residual capacity is 1,
* next item has weight 1. Optimal solution
* next item has weight 2. Select just one coin with largest value

Question 2

Activity Selection Problem
We have N activities, for each of them we know its starting and ending time. Select the largest subset of non overlapping activities

Answer 2

• Sort by ending time
• Select the first activity
• Scan the activities and, if the starting time is greater than or equal to the previously selected activity, then select it

Θ(nlogn) time complexity

Question 3

Weighted Job scheduling
Given n jobs, a job is a weighted segment. Select a subset of non overlapping job of maximal Total Weight

Answer 3

Can be solved with DAG approach.

Θ(nlogn) solution: sort and process segments by ending time
WJS[j] = best weight you can get with the first j segments
WJS[j] = max{ WJS[j-1], WJS[i] + Wj }, where i is the largest index i such that ei <= sj

Find i by keeping segments sorted. Done in logn time by searching the predecessor of sj

Another explanation:
Sort jobs by ending time.
dp[time] = profit means that within the first ‘time’ duration, we can make at most ‘profit’ money.
Initial dp[0] = 0, as we make profit = 0 at time = 0.
For each job = [s, e, p], where s,e,p are its start time, end time and profit, then the logic is similar to the knapsack problem: if we don’t do this job, nothing will be changed; if we do this job, binary search in the dp to find the largest profit we can make before start time s. So we also know the maximum current profit that we can make doing this job.
Compare with last element in the dp, if we make more money, it is worth doing this job, then we add the pair of [e, cur] to the back of dp. Otherwise, we’d like not to do this job.

Question 4

Job sequency problem
You have multiple jobs. Each job has a deadline and a profit. Each job takes 1 unit of time. Select jobs before their deadlines in order to maximize the total profit

Answer 4

Greedy strategy:
* Process jobs by their profit
* For each job, select the rightmost empty slot

Keep track of empty slots with a BBST and search for predecessor of current deadline

Θ(nlogn) time complexity