Maximum profit in job scheduling

Array Binary Search Dynamic Programming Sorting

54.6% acceptance

Feb 25, 2026

7274

122

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time X you will be able to start another job that starts at time X.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
    let n = start_time.len();
    let mut jobs: Vec<(i32, i32, i32)> = (0..n)
      .map(|i| (end_time[i], start_time[i], profit[i]))
      .collect();
    jobs.sort();

    // dp[i] = max profit using first i jobs (sorted by end time)
    let mut dp = vec![0i32; n + 1];
    let ends: Vec<i32> = jobs.iter().map(|&(e, _, _)| e).collect();

    for i in 1..=n {
      let (end, start, prof) = jobs[i - 1];
      // Binary search for last job ending <= start
      let j = ends[..i - 1].partition_point(|&e| e <= start);
      dp[i] = dp[i - 1].max(dp[j] + prof);
      let _ = end;
    }
    dp[n]
  }
}