Weighted interval job scheduling

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

Arrange the jobs in order of their starting times (earliest to latest). Pick a job from the sorted list. Identify the next job in the list that doesn't overlap with the selected job (i.e., its start time is after the selected job's end time). Repeat this process for the remaining jobs, starting from the next non-overlapping job. Determine and return the combination of jobs that results in the highest count of non-overlapping jobs.

• Python
• Javascript
•  Run

def count(jobs):
  if len(jobs) == 0:
    return 0

  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:]))

  return result

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

mx = 0

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

print(count(data))

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

  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)));
    }
  } 

  return result;
}

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));