Job Scheduling Algorithm

An array of jobs along with their deadline and profit (if job completes within deadline) where every job takes single unit of time. Maximize total profit if only one job can be scheduled at a time.

Applications

Complexity

  • Time:
  • Space:

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

    const jobId = ['a', 'b', 'c', 'd', 'e'];
const deadline = [2, 1, 2, 1, 3];
const profit = [100, 19, 27, 25, 15];
const N = deadline.length;
// sort according to decreasing order of profit
// Bubble sort implemented ... Implement a better algorithm for better performance
for (let i = 0; i < N - 1; i++) {
  for (let j = 0; j < N - i - 1; j++) {
    if (profit[j] < profit[j + 1]) {
      let temp = profit[j];
      profit[j] = profit[j + 1];
      profit[j + 1] = temp;
      temp = deadline[j];
      deadline[j] = deadline[j + 1];
      deadline[j + 1] = temp;
      const t = jobId[j];
      jobId[j] = jobId[j + 1];
      jobId[j + 1] = t;
    }
  }
}

const slot = new Array(N);
const result = new Array(N);
for (let i = N - 1; i >= 0; i--) {
  result[i] = '-';
}

// Initialise all slots to free
for (let i = 0; i < N; i++) {
  slot[i] = 0;
}

// Iterate through all the given jobs
for (let i = 0; i < N; i++) {
  /*
     Start from the last possible slot.
     Find a slot for the job
     */
  
  for (let j = Math.min(N, deadline[i]) - 1; j >= 0; j--) {
    if (slot[j] === 0) {
      
      result[j] = jobId[i];
      slot[j] = 1;
      
      break;
    }
  }
  
}