Is this scheduling problem with arrival times, deadlines, and costs NP-hard?

Question

There are $n$ jobs where each job $i$ has an arrival time $r_i$, a deadline $d_i$ and a cost $c_i$. The problem is to find a scheduling time $t_i$ (where $r_i\leq t_i\leq d_i$) for each job $i$ in order to minimize $$\sum_i\max_{j\in S_i}(c_j),$$ where $S_i$ is the set of jobs scheduled at time $t_i$.

Can we solve this problem in polynomial-time or is it NP-hard?

For example, if all jobs can be scheduled at the same time $t$, then the objective will be $\max(c_1,c_2,\ldots,c_n)$. The issue is that all jobs cannot always be scheduled at the same time $t$ because of their arrival times and deadlines. If I schedule the jobs as they arrive, I may end up with the objective of $\sum_{i=1}^nc_i$, which is the largest possible. So, the problem is somehow how to partition the jobs into sets $S_i$ (where jobs in $S_i$ are scheduled at the same time) for which we obtain the minimum objective. As such, I am trying to reduce Partition to this scheduling problem but still did not find the right reduction. Do you have any hints?

Answer 1

The following observation enables a polynomial-time algorithm:

Whenever the time slot $t_i$ for a job $i$ has been chosen, it's optimal to assign the same time slot for all lower-cost jobs that overlap $t_i$, as doing so will incur zero additional cost. Therefore, choosing the time slot for the most costly job "magnetises" all the jobs that can be assigned the same time slot, and partitions the remaining jobs into two sets: those whose intervals are completely to the left of this time slot, and those whose intervals are completely to the right. The subproblems for these two sets of jobs can then be solved independently.

A general subproblem can be described by an interval $(a, b)$ and a maximum cost $c$: the jobs in this subproblem consist of all those jobs whose intervals fall within $(a, b)$ and which have cost at most $c$. The optimal solution for a subproblem can be found by trying every possible time slot for the most costly job in the subproblem, and solving the corresponding 2 subproblems for each attempt. A plain recursive strategy would take exponenential time, but there are only $O(n^3)$ distinct subproblems to solve: There are only $O(n)$ "basic intervals" (maximal intervals that do not cross the beginning or end of any job interval) to consider, so there are at most $O(n^2)$ possible intervals (blocks) of these, and $O(n)$ possible different job costs. Thus dynamic programming can be applied. It should be possible to test each of the $O(n)$ possible time slots available for the most costly job in $O(1)$ time each, excluding the time needed to solve subproblems, for $O(n^4)$ time and $O(n^3)$ space overall -- not fast, but certainly polynomial.