Weighted Reservation Schedule
Hard About 40 min Free, no account needed
Choose a maximum-value set of nonoverlapping reservations with a mandatory cleanup gap.
The brief
A studio receives reservations packed as triples: [start, end, value, start, end, value, ...]. Select reservations with maximum total value. A selected reservation blocks [start, end) and then requires cleanup time units before the next selected reservation may start.
Solve([0, 2, 5, 2, 4, 6, 0, 4, 10], 0) returns 11, choosing the first two bookings. With cleanup 1, those bookings conflict and the answer is 10.
Input triples may be in any order. There are at most 100,000 triples; 0 <= start < end <= int.MaxValue, value is a nonnegative 32-bit integer, and cleanup is nonnegative. Duplicate triples represent separate requests but still conflict. Empty input returns 0. Return a 64-bit value and do not sort or change the caller's array.
Starter code
using System;
public class Solution
{
public long Solve(int[] reservations, int cleanup)
{
// TODO: implement the contract without changing the input.
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
- Binary search
- Halve a sorted search space, with exact boundaries and no off-by-one drift.
Related katas
- Longest Increasing Subsequence Medium Free Length of the longest strictly increasing subsequence - faster than the quadratic DP.
- Minimum Travel Pass Cost Medium Free Cover sparse travel dates with overlapping pass durations while paying for no unnecessary calendar state.
- Edit Distance Hard Free Fewest single-character edits turning one word into another.
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.