14.10 Prefix Constraints
Many greedy algorithms operate under a simple principle: > A decision is either feasible or infeasible.
14.10 Prefix Constraints
Many greedy algorithms operate under a simple principle:
A decision is either feasible or infeasible.
Prefix-constrained problems are more subtle. A decision that appears feasible now may create an infeasible state later. The challenge is maintaining feasibility not only for the final solution but for every prefix of the construction process.
These problems appear in scheduling, streaming systems, bandwidth allocation, project planning, load balancing, and resource management. The common theme is that constraints must hold continuously throughout execution, not merely at completion.
This recipe introduces the prefix constraint pattern and develops a powerful greedy technique based on priority queues and local repairs.
Problem
Suppose a collection of jobs is given.
Each job requires:
- A processing time
- A deadline
A schedule is feasible if every prefix satisfies all deadline constraints.
Example:
| Job | Duration | Deadline |
|---|---|---|
| A | 4 | 4 |
| B | 2 | 6 |
| C | 4 | 8 |
| D | 3 | 9 |
The question is:
Which jobs should be accepted so that all accepted jobs can be completed before their deadlines?
Often the objective is:
- Maximize the number of accepted jobs.
- Maximize profit.
- Minimize discarded work.
A Simple Example
Consider:
| Job | Duration | Deadline |
|---|---|---|
| A | 2 | 5 |
| B | 2 | 6 |
| C | 3 | 6 |
Sort by deadline:
| Job | Duration | Deadline |
|---|---|---|
| A | 2 | 5 |
| B | 2 | 6 |
| C | 3 | 6 |
Process sequentially.
After A:
Total time = 2
Feasible:
2 ≤ 5
After B:
Total time = 4
Feasible:
4 ≤ 6
After C:
Total time = 7
Violation:
7 > 6
Something must be removed.
Which job should be discarded?
Naive Strategies
Several obvious approaches fail.
Remove the Most Recent Job
Discard C.
Result:
A + B
Feasible.
But not always optimal.
Remove the Earliest Job
Discard A.
Result:
B + C
Also feasible.
Again, not always optimal.
Remove the Smallest Job
Sometimes correct.
Often wrong.
The local choice lacks a clear justification.
We need a stronger principle.
Greedy Insight
Suppose a deadline violation occurs.
Current jobs:
| Job | Duration |
|---|---|
| A | 2 |
| B | 2 |
| C | 3 |
Total:
7
To restore feasibility, some duration must be removed.
Which removal helps most?
The answer is:
Remove the longest job.
Discarding the longest job recovers the maximum amount of time with a single deletion.
This leaves the largest possible capacity for future jobs.
Core Greedy Rule
Process jobs by increasing deadline.
Whenever a deadline violation occurs:
Remove the longest-duration job seen so far.
This may or may not be the most recently added job.
The choice depends only on duration.
Why Sorting by Deadline Matters
Deadlines create the prefix constraints.
Suppose jobs are processed in arbitrary order.
A violation detected at one position may tell us nothing about earlier deadlines.
Sorting creates a useful invariant:
When processing job i, only the deadline of job i needs to be checked.
This dramatically simplifies the problem.
Algorithm
Step 1
Sort jobs by increasing deadline.
Step 2
Maintain:
- Current total duration.
- Max-heap of accepted job durations.
Step 3
For each job:
Add its duration.
total += duration
Insert duration into heap.
Step 4
If:
total > current deadline
Remove the largest duration from the heap.
Subtract it from the total.
Continue.
Example Walkthrough
Input:
| Job | Duration | Deadline |
|---|---|---|
| A | 5 | 5 |
| B | 2 | 6 |
| C | 3 | 8 |
| D | 2 | 9 |
Process A
Total = 5
Feasible.
Heap:
[5]
Process B
Total = 7
Violation:
7 > 6
Remove longest duration.
Remove:
5
New total:
2
Heap:
[2]
Process C
Total = 5
Feasible.
Heap:
[3,2]
Process D
Total = 7
Feasible.
Final accepted jobs:
B C D
Three jobs accepted.
Why Removing the Longest Job Works
Suppose a violation occurs.
Current duration:
T
Deadline:
D
We know:
T > D
At least one job must be removed.
Suppose:
x
is the longest duration among accepted jobs.
Removing any shorter job:
y < x
recovers less time.
Therefore:
- Feasibility improves less.
- Future scheduling flexibility is reduced.
The longest job dominates every alternative removal.
Exchange Argument
Assume an optimal solution removes a shorter job:
y
while retaining a longer job:
x
with:
x > y
Exchange them.
Remove:
x
instead.
Total processing time decreases further.
All deadlines remain satisfied.
Future capacity increases.
The modified solution is at least as good.
Therefore an optimal solution exists that removes the longest job.
The greedy choice is safe.
Heap-Based Implementation
The heap stores durations of accepted jobs.
Whenever a violation occurs:
extract maximum duration
This operation takes:
O(log n)
making the overall algorithm efficient.
Go Implementation
Job definition:
type Job struct {
Duration int
Deadline int
}
Sorting:
sort.Slice(jobs, func(i, j int) bool {
return jobs[i].Deadline < jobs[j].Deadline
})
Core loop:
total := 0
for _, job := range jobs {
total += job.Duration
heap.Push(maxHeap, job.Duration)
if total > job.Deadline {
longest := heap.Pop(maxHeap).(int)
total -= longest
}
}
Remaining heap elements correspond to accepted jobs.
Complexity Analysis
Sorting:
O(n log n)
Heap insertions:
O(n log n)
Heap removals:
O(n log n)
Total:
O(n log n)
Space:
O(n)
Real-World Applications
Course Scheduling
Universities often face:
- Limited semesters
- Course duration constraints
- Graduation deadlines
A variant of this problem determines the maximum number of courses that can be completed.
Cloud Resource Allocation
Jobs compete for finite execution windows.
Long-running tasks may need to be rejected to preserve service guarantees.
Manufacturing
Production orders have due dates.
Removing the largest order may allow many smaller orders to succeed.
Project Planning
Large tasks sometimes block numerous smaller milestones.
Selective removal can maximize overall throughput.
Common Mistakes
Removing the Most Recent Job
The newest job is not necessarily the most expensive.
Removing the Earliest Deadline Job
Deadlines determine ordering, not removal priority.
Removing the Smallest Job
This recovers the least time and often produces poor schedules.
Ignoring Prefix Feasibility
Checking only the final schedule misses violations that occur earlier.
The entire algorithm is built around maintaining prefix constraints.
Relationship to Earlier Greedy Patterns
Interval scheduling:
Choose earliest finish.
Job sequencing:
Choose highest profit.
Minimum refueling:
Choose largest available fuel.
Prefix constraints:
When overloaded, remove the largest duration.
All follow the same design philosophy:
- Maintain a feasible partial solution.
- Detect violations immediately.
- Apply a locally optimal repair.
- Continue processing.
Takeaway
Prefix-constrained scheduling problems require every intermediate state to remain feasible. By sorting jobs according to deadlines and removing the longest-duration job whenever a violation occurs, we maintain the largest possible future scheduling capacity. A max-heap supports efficient repairs, producing an (O(n \log n)) algorithm. This pattern appears repeatedly in modern scheduling, resource allocation, and throughput optimization systems, making it one of the most useful greedy techniques beyond the classical textbook examples.