Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number, bonus points for only assuming comparability), if she misses the deadline.
Write a function that given a list of (deadline, grade impact) figures out a schedule for which homework to do on which day that minimizes the sum of bad impact on her grades.
All homework has to be done eventually, but if she misses a deadline for an item, it doesn't matter how late she turns it in.
In an alternative formulation:
ACME corp wants to supply water to customers. They all live along one uphill street. ACME has several wells distributed along the street. Each well bears enough water for one customer. Customers bid different amounts of money to be supplied. The water only flows downhill. Maximize the revenue by choosing which customers to supply.
We can sort the deadlines using bucket sort (or just assume we have already sorted by deadline).
We can solve the problem easily with a greedy algorithm, if we sort by descending grade impact first. That solution will be no better than O(n log n).
I am looking for:
- a (potentially randomized) linear time algorithm
- or alternatively an argument that linear time is not possible
As a stepping stone:
- I have already proven that just knowing which items can be done before their deadline, is enough to reconstruct the complete schedule in linear time. (That insight is underlying the second formulation where I am only asking about certificate.)
- A simple (integral!) linear program can model this problem.
- Using duality of this program, one can check a candidate proposed solution in linear time for optimality, if one is also given the solution to the dual program. (Both solutions can be represented in a linear number of bits.)
Ideally, I want to solve this problem in a model that only uses comparison between grade impacts, and does not assume numbers there.
I have two approaches to this problem---one based on treaps using deadline and impact, the other QuickSelect-like based on choosing random pivot elements and partitioning the items by impact. Both have worst cases that force O(n log n) or worse performance, but I haven't been able to construct a simple special case that degrades the performance of both.