Hard · Intervals

Weighted job scheduler

Given an array jobs of {start, end, profit} (start < end) in any order, return the maximum total profit of a set of jobs no two of which overlap in time, where a job may start exactly when another ends.

Examples

Example 1

{
  "jobs": [
    {"start": 1, "end": 3, "profit": 50},
    {"start": 3, "end": 5, "profit": 20},
    {"start": 6, "end": 19, "profit": 100},
    {"start": 2, "end": 100, "profit": 200}
  ]
}

Output: profit 200

Example 2

{
  "jobs": [
    {"start": 1, "end": 2, "profit": 50},
    {"start": 3, "end": 5, "profit": 20},
    {"start": 6, "end": 9, "profit": 100},
    {"start": 1, "end": 4, "profit": 70},
    {"start": 5, "end": 7, "profit": 60}
  ]
}

Output: profit 170

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.