Skip to content
Katabench
Try free
7 min read The Katabench team

Weighted interval scheduling with a cleanup gap

Choose the most valuable compatible bookings for one room. Trace the scheduling table, find predecessors by finish time, and handle cleanup at the boundary.

A recording studio can take three short sessions that earn 18 credits, or two sessions that earn 19. A scheduler rewarded for filling slots picks the three. If the studio invoices by the session value, it should take the two. Adding a single high-paying request makes another tempting rule fail: the 15-credit session takes the room for the whole shift.

Here is the request sheet. Times are in hours from the start of the shift. Every accepted session uses the only room, and the engineer needs one hour to reset it before the next session starts. The studio may decline any request. Its only objective here is the sum of the credits it accepts.

Request Start End Credits Room ready again
A 0 2 4 3
B 1 4 11 5
C 3 5 7 6
D 5 7 8 8
E 6 8 7 9
F 0 8 15 9

Earliest finish takes A, C and E. Highest payout takes F. Spend a moment looking for the winner before building a table. D starts at 5, exactly when B releases the room. Together they earn 19. A scheduler that insists on an extra gap after the reset would lose that booking pair as well.

Price the two ways a schedule can end

Arrange the requests by finish time, then ask for the best payout among the first few rows. When D joins the sheet, every possible schedule falls into one of two groups. Schedules that decline D were already possible with A, B and C. Schedules that accept D can use any earlier requests whose reset finishes by hour 5. Only A and B meet that cutoff. The best schedule among those earns 11, so the best schedule ending with D earns 19.

The two alternatives when request D arrives
  1. Prefix before D

    1. A · 4
    2. B · 11
    3. C · 7

    Declining D keeps a best value of 11. Either B alone or A with C earns that much.

  2. Prefix compatible with D

    1. A · 4
    2. B · 11

    Only these requests leave the room ready by hour 5. The best payout in this prefix is B's 11.

  3. Accept D

    1. B · 11
    2. D · 8

    The reset fills hour 4 to hour 5. These two bookings earn 19.

Define best[k] as the maximum payout using the first k requests in finish order. An empty prefix earns zero. For the request at zero-based index i, let p be the number of preceding requests compatible with its start. Those compatible requests form a prefix because every room-ready time is a finish time plus the same cleanup. The best payout in that entire prefix is already in best[p]. It might itself come from several requests.

Text
decline = best[i]
accept  = value[i] + best[p]
best[i + 1] = max(decline, accept)

The predecessor lookup tells you how much of the sheet is still available. The table tells you what that part of the sheet is worth.

Choosing the last compatible request directly can lose money. Imagine two overlapping requests in that prefix, the earlier-finishing one worth 11 and the later-finishing one worth 1. Either leaves time for the new session. The prefix maximum keeps the 11-credit option alive when the search boundary happens to land on the 1-credit row. This separation between a time boundary and a value is the basis of the weighted interval scheduling recurrence. Princeton's notes on weighted interval scheduling

Count compatible requests with an upper bound

Scanning backwards from every session works and makes a good first implementation. Its cost depends on the shape of the requests. If all sessions start at zero and each finishes a bit later than the previous one, there are no compatible predecessors. A backwards search that walks to the start of the sheet for each request examines roughly half the sheet per lookup. Sorting once gives you enough structure to do better.

Search the half-open range of preceding indices from zero to i, excluding i. Everything with a room-ready time at or before the new start belongs on the compatible side. Move past every such row, including all of the rows exactly at the cutoff. The resulting insertion point is the size of the compatible prefix. If no session fits it is zero, already a valid table index. This is another use of the boundary search in finding a minimum shipping capacity.

C#
static long BestPayout((int Start, int End, int Value)[] requests, int cleanup)
{
    var sorted = requests.OrderBy(request => request.End).ToArray();
    var best = new long[sorted.Length + 1];

    for (int i = 0; i < sorted.Length; i++)
    {
        var current = sorted[i];
        int low = 0;
        int high = i;
        while (low < high)
        {
            int middle = low + (high - low) / 2;
            long ready = (long)sorted[middle].End + cleanup;
            if (ready <= current.Start)
                low = middle + 1;
            else
                high = middle;
        }

        long accept = best[low] + current.Value;
        best[i + 1] = Math.Max(best[i], accept);
    }

    return best[sorted.Length];
}

The method expects valid requests with a nonnegative start, a strictly later end, a nonnegative value and a nonnegative cleanup duration. It orders a private copy so callers can continue to use arrival order. Two requests with the same finish time cannot follow one another under these rules. Either can come first in the sorted list without changing the optimal payout. If requests ever have different cleanup durations, sort by the instant the room becomes available again to preserve the ordered lookup.

Use wide arithmetic in two places. If a booking ends at int.MaxValue, adding one hour of cleanup in a 32-bit integer could make the room appear available before it was booked. The cast has to happen before addition. Two compatible sessions can also earn more than a signed 32-bit integer can hold between them, even if each one's value fits on the request sheet. The table uses 64-bit totals throughout.

Read a decision back out of the table

For the six rows above, including the empty prefix, the stored values are 0, 4, 11, 11, 19, 19, 19. Reading the last entry gives the invoice total. It doesn't identify every session on the invoice. B and C both leave their prefix at 11, and a table that kept only those numbers has deliberately forgotten how many different schedules attained them.

To recover one optimal schedule, walk backwards from the last row. If declining the row explains its best value, skip it. Otherwise include that request and jump to its compatible prefix. On this sheet you skip F, skip E, include D, jump back to the end of the A/B prefix, and include B. Record the predecessor counts during the forward pass if you'll need that walk. Choosing to skip on equality supplies a consistent tie rule for a fixed row order. A business rule such as preferring the schedule with fewer resets would require carrying that second objective through the comparison.

Check the edge where the room changes hands

Take just B and D. With cleanup one the pair earns 19. Raise cleanup to two and the answer falls to 11. Reverse the input and both answers should stay the same. A pair of identical requests checks a different mistake: taking both would book the same room twice. For broader coverage, enumerate subsets of a short sheet, sort each subset chronologically and discard any that violate a reset. The most valuable surviving subset is an independent check on both the predecessor search and the recurrence.

With n requests the sort and the n binary searches take O(n log n) time in total. The ordered copy and table take O(n) space. The Katabench performance guide explains how input growth affects an algorithm submission. The Weighted Reservation Schedule exercise among the C# coding challenges accepts unsorted request triples and adds a practical constraint: the caller must get its original array back in the same order.

Practice what you just read

More like this: C# coding challenges →

Get new katas and .NET tips in your inbox

A short note when fresh kata land, plus the C# and performance tricks behind the grading. No spam, unsubscribe anytime.