Skip to content
Katabench
Try free

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

C#
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.

C# coding challenges →

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