Maximum Profit in Job Scheduling

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

Solution to Smallest Sufficient Team

This is my solution for the LeetCode problem number 1125, Smallest Sufficient Team.

This problem is a version of a well-known NP-complete problem in computer science known as the set cover problem. In order to make the solution fast enough to pass the time limit, redundant people are removed from the set of candidates. If \(s_i\) denotes the set of skills of person \(i\) and \(s_i \cup s_j = s_i\), person \(j\) is redundant, as it does not do anything more than \(i\) can and therefore is not required to find an optimal solution.

Another possible optimization would be to determine if there are any required people. Where a required person would be one that possesses a skill no other person does. This person simply has to be part of the solution and can be removed from the search and added to the solution unconditionally.

The required skills and each person’s skills are represented by 16-bit unsigned integers, because computing their union is much faster than computing the union of vectors of strings. After this, it basically becomes a matter of considering each person and exhaustively testing all of the possible solutions. Sorting the vector of people from “most skilled” to “least skilled” may also speed up the search considerably. Lastly, the search can stop whenever the current solution being built gets to be as large as the best one found so far.

The C++ implementation can be found here.

Solution to Best Time to Buy and Sell Stock with Cooldown

This is my solution for the LeetCode problem number 309, Best Time to Buy and Sell Stock with Cooldown.

This is a quite simple problem which can be addressed in O(1) space and O(n) time using dynamic programming. However, the O(n) space solution seems easier to arrive at. The subproblem explored through dynamic programming is that starting day \(i\) with no stock and after the cooldown has ended is equivalent to solving the original problem with only days \(i\) through \(n\).

In this solution, 0 is used to indicate that no stock is owned, 1 is used to indicate that stock is owned and 2 is used to indicate cooldown. The algorithm keeps three values for each day: the maximum profit by starting without stock, the maximum profit by starting with stock and the maximum profit by starting under cooldown. After the bottom-up solving is done, the answer to the problem question is what is the maximum profit for starting at the first day without stock.

int maxProfit(const vector<int> &prices) {
  vector<array<int, 3>> m(prices.size() + 1);
  for (int i = prices.size() - 1; i >= 0; i--) {
    m[i][0] = max(m[i + 1][0], m[i + 1][1] - prices[i]);
    m[i][1] = max(m[i + 1][1], m[i + 1][2] + prices[i]);
    m[i][2] = max(m[i + 1][2], m[i + 1][0]);
  }
  return m[0][0];
}

Now, because evaluating day \(i\) only requires information about day \(i + 1\), the vector of arrays can become just two arrays, as follows.

int maxProfit(const vector<int> &prices) {
  array<int, 3> d1{};
  array<int, 3> d2{};
  for (int i = prices.size() - 1; i >= 0; i--) {
    d2 = d1;
    d1[0] = max(d2[0], d2[1] - prices[i]);
    d1[1] = max(d2[1], d2[2] + prices[i]);
    d1[2] = max(d2[2], d2[0]);
  }
  return d1[0];
}

Path of Exile calculators

I recently developed a web-based Path of Exile calculator so that it is more practical to estimate the number of divine orbs required to get at least a certain set of rolls.

It can be found on its own page.

The JavaScript source code is not obfuscated so it is easier to reuse it if you want to.

The Future of WebAssembly

I was happy to read about what is planned for WebAssembly.

It is a really good thing to see what came after asm.js going so far. If we are transpiling to JS anyway, might as well compile to something which runs faster.

Lastly, I’d like to point out that the author has this blog which has some other well-made cartoons explaining web concepts.