Weighted job/interval scheduling – Activity Selection Problem

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

Example: 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 by scheduling jobs 1 and 4.

This problem also known as Activity Selection problem. From wiki, the activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (si) and finish time (fi). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time.

Assume there exist n activities with each of them being represented by a start time si and finish time fi. Two activities i and j are said to be non-conflicting if si ≥ fj or sj ≥ fi. The activity selection problem consists in finding the maximal solution set (S) of non-conflicting activities, or more precisely there must exist no solution set S' such that |S'| > |S| in the case that multiple maximal solutions have equal sizes.

Consider the following 6 activities.
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
The maximum set of activities that can be executed
by a single machine/job is {0, 1, 3, 4}.

Greedy Solution

• Sort the activities according to their finishing time
• Select the first activity from the sorted array and print it.
• For each of the remaining activities in the sorted array – If the start time of this activity is greater than the finish time of previously selected activity then select this activity and send it to output channel.

Greedy-Iterative-Activity-Selector(A, s, f): 
 
     Sort A by finish times stored in f
     
     S = {A[0]} 
     k = 0
     
     n = A.length
     
     for i = 1 to n-1:
        if s[i] ≥ f[k]: 
            S = S U {A[i]}
            k = i
     
     return S

We can also formulate the problem as follows –

You are given pairs of numbers. In a pair the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b < c.So you can form a long chain in the similar fashion. Find the longest chain which can be formed

For example, input set = {(1,2), (3,4), (0,6), (5,7), (8,9), (5,9)}. Then the longest chain formed is {(1,2), (3,4), (5,7), (8,9)}. Following is an O(nlgn) implementation of this problem .

    private static class Job implements Comparable<Job>{
		public int start;
		public int finish;
		public int weight;
		
		public Job(int start, int finish){
			this.start = start;
			this.finish = finish;
			this.weight = 1;
		}
		public Job(int start, int finish, int weight){
			this.start = start;
			this.finish = finish;
			this.weight = weight;
		}

		@Override
		public int compareTo(Job o) {
			return Integer.compare(this.finish, o.finish);
		}

		@Override
		public String toString() {
			return "[" + start + "," + finish + "]";
		}
		
		public void print(){
			System.out.println(this.toString());
		}
	}	

      public static int longestChain(Job[] pairs){
		Arrays.sort(pairs); //Assume that Pair class implements comparable with the compareTo() method such that (a, b) < (c,d) iff b<c
		int chainLength = 0;
		
		//select the first pair of the sorted pairs array
		pairs[0].print(); //assume print method prints the pair as “(a, b) ”
		chainLength++;
		int prev = 0;

		for(int i=1;i<pairs.length; i++)
		{
			if(pairs[i].start >= pairs[prev].finish)
			{
				chainLength++;
				prev = i;
			}
		}
		return chainLength;	
	}

Weighted Activity Selection Problem

The simple activity selection problem described above is a weighted specialization with weight = 1. Now, lets focus on generalized weighted activity selection problem. From wiki, The generalized version of the activity selection problem involves selecting an optimal set of non-overlapping activities such that the total weight is maximized. Although there was an O(nlgn) greedy solution for non-generic version but can we also solve the same logic for the weighted version? Certainly not because it involves a optimization of weight(or profit).

Speaking formally, Weighted activity selection problem –

• Job requests 1, 2, … , N.
• Job j starts at sj, finishes at fj , and has weight wj .
• Two jobs compatible if they don’t overlap.
• Goal: find maximum weight subset of mutually compatible jobs.

For example, suppose we have N=8 jobs {A,B,C,D,E,F,G,H} with the following start and finish time and weights {w1, w2,…,wN} respectively.

Let’s sort and label the jobs by finishing time: f1 ≤ f2 ≤ . . . ≤ fN. In order to maximize profit we can either take current job j and include to optimal solution or not include current job j to optimal solution. How to find the profit including current job? The idea is to find the latest job before the current job (in sorted array) that doesn’t conflict with current job 1<=j<=N-1. Once we find such a job, we recur for all jobs till that job and
add profit of current job to result.

Lets define qj = largest index i < j such that job i is compatible with j.. For example – q7 = 3, q2 = 0.

Optimal Substructure
Let MAX_PROFIT(j) = value of optimal solution to the problem consisting of job requests {1, 2, . . . , j }.

• Case 1: MAX_PROFIT selects job j.
  • can’t use incompatible jobs { qj + 1, qj + 2, . . . , j-1 }
  • must include optimal solution to problem consisting of remaining compatible jobs { 1, 2, . . . , qj }
• Case 2: MAX_PROFIT does not select job j.
  • must include optimal solution to problem consisting of remaining compatible jobs { 1, 2, . . . , j – 1 }

MAX_PROFIT(j) = 0 if j=0;
              = max{wj+MAX_PROFIT(qj), MAX_PROFIT(j-1)}; // max of including and excluding

Repeating Subproblems
For the example, we can see from the recursion tree of the example, there are lots of subproblems we need to recompute if we do plain recursion of the above optimal substructure.

Dynamic Programming (DP) Solution
When we have optimal substructure and repeating subproblems then natural solution would be to use DP to reuse the computation by caching subproblem solutions in a DP table. Following is an O(nlgn) solution.

Weighted-Activity-Selection(S):  // S = list of activities
  
       sort S by finish time
       MAX_PROFIT[0] = 0
      
       for j = 1 to n:
           qj = BST.floor(S[j].start)//binary search to find activity with finish time <= start time for j
           MAX_PROFIT[j] = MAX(MAX_PROFIT[j-1], MAX_PROFIT[qj] + w(j))
           
       return MAX_PROFIT[n]

Java Implementation – O(nlgn)

public static int weightedActivitySelection(Job[] jobs){
	int n = jobs.length;
	int profit[] = new int[n+1];
	int q[] = new int[n];
	
	//sort according to finish time
	Arrays.sort(jobs);
	
	//find q's - O(nlgn)
	q[0] = -1;
	for(int i = 1; i< n; i++){
		q[i] = binarySearchLatestCompatibleJob(jobs, 0, i-1, jobs[i].start);
	}
	
	//compute optimal profits - O(n)
	profit[0] = 0;
	for(int j = 1; j<=n; j++){
		int profitExcluding = profit[j-1];
		int profitIncluding = jobs[j-1].weight;
		if(q[j-1] != -1){
			profitIncluding += profit[q[j-1]+1];
		}
		profit[j] = Math.max(profitIncluding, profitExcluding);
	}
	return profit[n];
}