Is this scheduling problem with arrival times, deadlines, and costs NP-hard?
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.