Bernardo Sulzbach's Website

Maximum Profit in Job Scheduling

2019-10-21

This is my solution for the LeetCode problem number 1235, Maximum Profit in Job Scheduling.

This problem is quite similar to that of determining the maximum number of not overlapping ranges. The only difference is that in this problem the ranges have a profit associated with them, rather than a linear function over the size of the range.

The key idea for my solution, which runs in \(O(n \lg n)\), is to sort all jobs by their starting time and, going backwards, store the result of the maximum profit when starting at time \(t\). For every job that starts at \(t_i\), the maximum when starting at \(t_i\) has to be set to either the maximum found for any \(t_j > t_i\) or the maximum for any \(t_k > e_i\), where \(e_i\) is the ending time of the job \(i\), plus the profit of job \(i\), whichever is bigger. This is the optimization of the choice between scheduling job \(i\) or skipping it.

struct Job {
  int startTime;
  int endTime;
  int profit;

  Job(int startTime, int endTime, int profit) : startTime(startTime), endTime(endTime), profit(profit) {}

  bool operator<(const Job& rhs) const {
    if (startTime < rhs.startTime) return true;
    if (rhs.startTime < startTime) return false;
    if (endTime < rhs.endTime) return true;
    if (rhs.endTime < endTime) return false;
    return profit < rhs.profit;
  }
};

int firstEqualOrGreater(const map<int, int>& bestStartingFrom, int key) {
  return bestStartingFrom.upper_bound(key - 1)->second;
}

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
  vector<Job> jobs;
  for (size_t i = 0; i < startTime.size(); i++) {
    jobs.emplace_back(startTime[i], endTime[i], profit[i]);
  }
  // Sorting this vector is O(n lg n).
  sort(begin(jobs), end(jobs));
  map<int, int> bestStartingFrom;
  bestStartingFrom[numeric_limits<int>::max()] = 0;
  // Querying and inserting n times here is O(n lg n).
  for (auto it = rbegin(jobs); it != rend(jobs); it++) {
    const auto a = firstEqualOrGreater(bestStartingFrom, it->startTime);
    const auto b = it->profit + firstEqualOrGreater(bestStartingFrom, it->endTime);
    bestStartingFrom[it->startTime] = max(a, b);
  }
  return firstEqualOrGreater(bestStartingFrom, 0);
}

Related posts