Daily Archives: January 28, 2015

This problem is from G4G link. It is a pratice for DP.

Problem Description:
Given N jobs where every job is represented by following three elements of it.
1) Start Time
2) Finish Time.
3) Profit or Value Associated.
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Example:
Input: Number of Jobs n = 4
Job Details {Start Time, Finish Time, Profit}
Job 1:  {1, 2, 50}
Job 2:  {3, 5, 20}
Job 3:  {6, 19, 100}
Job 4:  {2, 100, 200}
Output: The maximum profit is 250.
We can get the maximum profit by scheduling jobs 1 and 4.
Note that there is longer schedules possible Jobs 1, 2 and 3
but the profit with this schedule is 20+50+100 which is less than 250.

Analysis:
This problem is quite similar to “Buy Sell stock to get maximum profit at most k times” and “0-1 knapsack” problem. First, all jobs should be ascending sorted by end time. I define 2 array: local[] and global[].
local[i] is the max profit when ith job is assigned by the time of job[i].end_time.
global[i] is the max profit by the time of job[i].end_time.

local[i] = job[i].profit + global[j]
the jth job is the first job before ith job, where job[j].end_time <= job[i].start_time. This process can be shorted to O(logn) time by binary search.
global[i] = max{ local[i], global[i – 1] }
At the job[i].end_time, the max is either the max profit when ith job is assigned, or global[i – 1]

The following is my code:

1. package dp;
2. import java.util.ArrayList;
3. import java.util.Collections;
4. import java.util.Comparator;
5. import java.util.List;
6. public class MaxWorkProfit {
7.     public static void main(String[] args) {
8.         Job j1 = new Job(1, 2, 50);
9.         Job j2 = new Job(3, 5, 20);
10.         Job j3 = new Job(6, 19, 100);
11.         Job j4 = new Job(2, 100, 200);
12.         Job j5 = new Job(19, 20, 60);
13.         Job j6 = new Job(20, 21, 60);
14.         List jobs = new ArrayList();
15.         jobs.add(j1);
16.         jobs.add(j2);
17.         jobs.add(j3);
18.         jobs.add(j4);
19.         jobs.add(j5);
20.         jobs.add(j6);
21.         int max_profit = getMaxProfit(jobs);
22.         System.out.println(max_profit);
23.     }
24.     public static int getMaxProfit(List job) {
25.         Collections.sort(job, new JobComparator());
26.         // local[i] is the max profit when jobi is assigned.
27.         int[] local = new int[job.size()];
28.         // global[i] is by the end time of jobi, the max profit.
29.         int[] global = new int[job.size()];
30.         local[0] = job.get(0).profit;
31.         global[0] = job.get(0).profit;
32.         for (int i = 1; i < job.size(); i++) {
33.             Job curr_job = job.get(i);
34.             // find the i, where endi<=startn. This find can be optimized to
35.             // binary search
36.             for (int j = i – 1; j >= 0; j–) {
37.                 if (job.get(j).end <= curr_job.start) {
38.                     local[i] = global[j];
39.                     break;
40.                 }
41.             }
42.             local[i] += curr_job.profit;
43.             global[i] = Math.max(local[i], global[i – 1]);
44.         }
45.         return global[job.size() – 1];
46.     }
47.     static class Job {
48.         int start;
49.         int end;
50.         int profit;
51.         Job(int start, int end, int profit) {
52.             this.start = start;
53.             this.end = end;
54.             this.profit = profit;
55.         }
56.     }
57.     static class JobComparator implements Comparator {
58.         public int compare(Job j1, Job j2) {
59.             return j1.end – j2.end;
60.         }
61.     }
62. }