Given n jobs where every job has the start time, finish time and profit associated. Find the maximum profit in scheduling jobs such that no two jobs overlap.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Weighted interval job scheduling, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

def count(jobs):
  if len(jobs) == 0:
    return 0
  
  global cache
  if not cache[len(jobs) - 1]:
    result = jobs[0][2]

    for i in range(1, len(jobs)):
      if jobs[i][0] >= jobs[0][1]:
        result = max(result, jobs[0][2] + count(jobs[i:]))

    cache[len(jobs) - 1] = result

  return cache[len(jobs) - 1]

data = [
  [1, 2, 50], 
  [3, 5, 20],
  [6, 19, 100],
  [2, 100, 200]
]

cache = [None] * len(data)

mx = 0

for i in range(len(data)):
  mx = max(mx, count(data[i:]))

print(count(data))

// Javascript implementation

const cache = [];

function count(jobs) {
  if (jobs.length === 0) {
    return 0;
  }

  if (cache[jobs.length - 1] === undefined) {
    let result = jobs[0][2];

    for (let i = 1; i < jobs.length; i++) {
      if (jobs[i][0] >= jobs[0][1]) {
        result = Math.max(result, jobs[0][2] + count(jobs.slice(i)));
      }
    } 

    cache[jobs.length - 1] = result;
  }

  return cache[jobs.length - 1];
}

const data = [
  [1, 2, 50], 
  [3, 5, 20],
  [6, 19, 100],
  [2, 100, 200]
];

let max = 0;

for (let i = 0; i < data.length; i++) {
  max = Math.max(max, count(data.slice(i)));
}

console.log(count(data));

Weighted interval job scheduling (Memoization)

Hint