Maximum Task Value

Question Description

Consider we are given a set of tasks, with startTime, endTime and value. For certain task, startTime <= endTime, indicates task time range [startTime, endTime]

Now we need to choose as many not intersected tasks as possible to maximize the total value of chosen tasks. (Note that endTime is considered in the time range, so [1, 2] and [2, 3] is intersected)

You could also checkout the related Leetcode question Maximum Profit In Job Scheduling

Analysis

My first thought is to use DynamicProgramming to solve this question.

Consider we’ve already known the best solution when only considering time period [t + 1, infty], that is, we already known solution[k] in which $k\in [t+1,+\infty )$.

And now, we consider task Ti.

Note

solution[t] here means the maximum sum of value we choose achieve by ONLY selecting tasks that startTime and endTime falls into the range [t, infty].

infty here refers to $+\infty$.

Case1: Choose task Ti

In this case, the task we could choose is:

• Task Ti
• All the other tasks that need to be chosen to make range [Ti.endTime + 1, infty] reach’s the maximum value solution[Ti.endTime + 1]

the new value sum will be:

solution[i] = Ti.value + solution[Ti.endTime + 1]

Case2: Not Choose task Ti

In this case, since nothing changed compared to previous state, we have:

solution[i] = solution[i + 1]

Sort Task By Time

Notice above, we have one of the state transfer formula:

solution[i] = solution[i + 1]

To ensure solution[i + 1] is the best solution we could found, when processing Ti, all task start later than i must be already considered.

In order to satisfy this, we could sort task by it’s startTime and iterate from the one with largest startTime to the one with smallest startTime. By doing this, when processing Ti with start time t, all tasks that starts later then t will be iterated before, thus, already considered.

Note

The state transfer equation and the iteration above use the direction from the largest startTime to smallest. However, it’s easy to proof that the iteration could goes from the smallest to the largest as well.

In this case, we need to use sort criteria endTime instead of startTime to sort the array, and the state transfer equation should also be modified:

solution[i] = Ti.value + solution[Ti.startTime - 1];

or

solution[i] = solution[i - 1];

Code Implementation

Leetcode Question Link

#include <iostream>
#include <vector>
#include <algorithm>
#include <format>
using LL = long long;
using std::cout, std::endl;
using std::vector;
 
const bool debug = false;
 
// task struct
struct Task
{
    int start;
    int end;
    int value;
};
// < override for task struct
bool operator<(const Task &ta, const Task &tb)
{
    return ta.end < tb.end;
}
 
std::ostream &operator<<(std::ostream &os, const Task &t)
{
    os << std::format("<Task start={}  end={}  value={}>", t.start, t.end, t.value);
    return os;
}
 
struct SolutionData
{
    int time;
    int value;
    SolutionData() : time(0), value(0) {}
    SolutionData(int time, int value) : time(time), value(value) {}
};
 
bool operator<(const SolutionData &sa, const SolutionData &sb)
{
    return sa.time < sb.time;
}
 
std::ostream &operator<<(std::ostream &os, const SolutionData &so)
{
    os << std::format("[time={}, value={}]", so.time, so.value);
    return os;
}
 
const int MAX_SIZE = 50010;
 
// global variables
Task tasks[MAX_SIZE];
int size = 0;
 
// store the solutions
int solutionSize = 0;
SolutionData solutions[MAX_SIZE];
 
SolutionData &getLastSolution()
{
    return solutions[solutionSize - 1];
}
 
int getSolutionValue(int time)
{
    const SolutionData &lastSolution = getLastSolution();
    if (time < 0)
        time = 0;
 
    const SolutionData *sd;
    if (time > lastSolution.time)
    {
        sd = &lastSolution;
        if (debug)
        {
            cout << "use last solution as answwer: " << (*sd) << endl;
        }
    }
    else
    {
        if (debug)
        {
            cout << "solutionSize: " << solutionSize << endl;
            cout << "lower bound serach range: " << *solutions << " to " << *(solutions + solutionSize) << endl;
        }
        sd = std::lower_bound(solutions, solutions + solutionSize, SolutionData(time, 0));
        if (debug)
        {
            cout << "lower bound got: " << (*sd) << endl;
        }
        if (sd->time > time)
            sd -= 1;
        if (debug)
        {
            cout << "use lower bound as answwer: " << (*sd) << endl;
        }
    }
 
    if (debug)
    {
        cout << "solution time=" << time << " is " << (*sd) << endl;
    }
 
    return sd->value;
}
 
// set new solution in solutions array with basic checking
void setSolution(const SolutionData &newSolution)
{
    if (debug)
    {
        cout << "got new solution update request: " << newSolution << endl;
    }
 
    SolutionData &lastSolution = getLastSolution();
 
    if (newSolution.time < lastSolution.time)
    {
        cout << "[Warning] Should not update solution time earlier than previous" << endl;
        return;
    }
 
    if (newSolution.value <= lastSolution.value)
    {
        cout << "[Warning] Should not update solution value smaller than previous" << endl;
        return;
    }
 
    if (newSolution.time == lastSolution.time)
    {
        lastSolution.value = newSolution.value;
    }
    else
    {
        solutions[solutionSize++] = newSolution;
    }
 
    if (debug)
    {
        cout << "solution updated: " << getLastSolution() << endl;
    }
 
    return;
}
 
class Solution
{
public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit)
    {
 
        solutionSize = 0;
        int size = profit.size();
        for (int i = 0; i < size; ++i)
        {
            // startTime + 1 to match time-slot indexing instead of time point indexing
            // in time-slot indexing, endTime is also considered into the time range,
            // E.g. [1, 2] and [2, 3] are intersected
            tasks[i] = Task(startTime[i] + 1, endTime[i], profit[i]);
        }
 
        // sort task by `start`
        std::sort(tasks, tasks + size);
 
        // init solutions
        solutions[0] = SolutionData();
        solutionSize += 1;
        // dp to get solution
        for (int i = 0; i < size; ++i)
        {
            Task &curTask = tasks[i];
            if (debug)
            {
                cout << "currently processing: " << curTask << endl;
            }
            int valueNotChoosed = getLastSolution().value;
            int valueChoosed = getSolutionValue(curTask.start - 1) + curTask.value;
 
            if (valueChoosed > valueNotChoosed)
            {
                setSolution(SolutionData(curTask.end, valueChoosed));
            }
        }
 
        return getLastSolution().value;
    }
};