Oya Code Notes

Maximum Task Value - With Max Task Limit

4 min read

Note

This note is an extension to Maximum Task Value, please read that first

Now consider what will happen if we add limit to the task count we could choose in total, say . That means we could choose at most different tasks, then in this case, what’s the maximum profit?

You could also checkout the related Leetcode question Two Best Non-overlapping Events

Analysis

We could consider this DynamicProgramming question with two constrain:

  • Constrain 1: Task time period could not overlap
  • Constrain 2: Task count

In this case, the original transfer equation becomes:

// not choose
solutions[layer][i] = solutions[layer][i - 1]
// choosed
solutions[layer][i] = Ti.value + solutions[layer - 1][Ti.start - 1]

Layer 1 Solution Calculation

We already know for layer , the solution is always . Consider that is we are only allow to choose at most items, then the best maximum sum of value we got should always be zero.

Then based on transfer equation above:

// not choose
solutions[1][i] = solutions[1][i - 1]
// choosed
solutions[layer][i] = Ti.value

It’s easy to proof that such transfer equation is actually mean to always choose the single one task with maximum value in time period [0, i]. This is intuitive, since when only one task it allowed, we don’t need to think things like time-overlapping, we just always choose one task that with maximum value.

Code Implementation

#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
vector<Task> tasks;
int size = 0;
 
void initTasks()
{
    tasks.clear();
    tasks.reserve(MAX_SIZE);
}
 
using SolutionVec = vector<SolutionData>;
 
// usage: Solution solutions[layer][time];
SolutionVec solutions[3];
 
SolutionData &getLastSolution(int layer)
{
    return solutions[layer].back();
}
 
int getSolutionValue(int layer, int time)
{
    time = std::max(time, 0);
 
    const SolutionData &lastSolution = getLastSolution(layer);
 
    // target time > maximum solution time
    // don't need binary search anymore, the last solution is the maximum possible solution
    // at this point (this assumption relies on the iteration order of low endTime to high endTime)
    if (time > lastSolution.time)
    {
        return lastSolution.value;
    }
    else
    {
        // search on specified layer
        auto &curLayerSolution = solutions[layer];
 
        auto res = std::lower_bound(curLayerSolution.begin(), curLayerSolution.end(), SolutionData(time, 0));
        if ((*res).time > time)
        {
            --res;
        }
 
        return (*res).value;
    }
}
 
// set new solution in solutions array with basic checking
void setSolution(int layer, const SolutionData &newSolution)
{
 
    SolutionData &lastSolution = getLastSolution(layer);
 
    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[layer].push_back(newSolution);
    }
}
 
// use data in tasks array to initial layer 0 and layer 1 solutions
// also add initial (time=0, value=0) solution to layer 2
// require task to be sorted by endTime
void initSolutions()
{
    auto &s = solutions;
    for (int l = 0; l < 3; ++l)
    {
        s[l].clear();
        s[l].emplace_back(SolutionData());
    }
 
    // layer 1
    for (const auto &t : tasks)
    {
        SolutionData &last = getLastSolution(1);
        if (t.value > last.value)
        {
            setSolution(1, SolutionData(t.end, t.value));
        }
    }
}
 
void initLayer2Solution()
{
    int notChoose, choose;
    for (const auto &curTask : tasks)
    {
        notChoose = getLastSolution(2).value;
        choose = curTask.value + getSolutionValue(1, curTask.start - 1);
 
        if (choose > notChoose)
        {
            setSolution(2, SolutionData(curTask.end, choose));
        }
    }
}
 
class Solution
{
public:
    int maxTwoEvents(vector<vector<int>> &events)
    {
        // init and format tasks
        initTasks();
        for (const auto &taskData : events)
        {
            tasks.emplace_back(Task(taskData[0], taskData[1], taskData[2]));
        }
        // sort tasks
        std::sort(tasks.begin(), tasks.end());
 
        // init solutions
        initSolutions();
        initLayer2Solution();
 
        return getLastSolution(2).value;
    }
};

Graph View