Knapsack Problem

322. Coin Change

Java

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];   
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int k : coins) {
                if (i - k < 0 || dp[i - k] == Integer.MAX_VALUE) continue;
                dp[i] = Math.min(dp[i], dp[i - k] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

Python

    def coinChange(self, coins, amount):
        dp = [0] + [float('inf')] * amount
        
        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] = min(dp[i], dp[i-coin]+1)
        
        return dp[-1] if dp[-1] != float('inf') else -1

1235. Maximum Profit in Job Scheduling

Rank all interviews by the end time.

public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    int n = startTime.length;
    Job[] jobs = new Job[n];
    for (int i = 0; i < n; i++) {
        jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
    }
    Arrays.sort(jobs, (o1,o2)->(o1.end - o2.end));
    int[] dp = new int[n];
    dp[0] = jobs[0].profit;
    for (int i = 1; i < n; i++) {
        int p = jobs[i].profit;
        int k = search(jobs, i);
        if (k != -1) {
            p += dp[k];
        }
        dp[i] = Math.max(dp[i - 1], p);
    }
    return dp[n - 1];
}

private int search(Job[] jobs, int i) {
    int left = 0, right = i - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (jobs[mid].end <= jobs[i].start) {
            if (jobs[mid + 1].end > jobs[i].start) {
                return mid;
            } else {
                left = mid + 1;
            }
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

class Job {
    int start, end, profit;
    Job(int s, int e, int p) {
        this.start = s;
        this.end = e;
        this.profit = p;
    }
}

TreeMap to store end time : max profit

public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    int n = startTime.length;
    int[][] jobs = new int[n][3];
    for (int i = 0; i < n; i++) {
        jobs[i] = new int[] {startTime[i], endTime[i], profit[i]};
    }
    Arrays.sort(jobs, (o1,o2)->(o1[1] - o2[1]));
    TreeMap<Integer, Integer> dp = new TreeMap<>();
    dp.put(0, 0);
    for (int[] job : jobs) {
        int curt = dp.floorEntry(job[0]).getValue() + job[2];
        if (curt > dp.lastEntry().getValue()) {
            dp.put(job[1], curt);
        }
    }
    return dp.lastEntry().getValue();
}
}