Ship Packages Within D Days
Medium About 20 min Free, no account needed
Smallest ship capacity that delivers the conveyor belt on schedule.
The brief
Packages with weights[i] must ship in order. Each day the ship loads
consecutive packages without exceeding its capacity. Return the minimum
capacity that ships everything within days days.
The obvious approach tries capacity max(weights), +1, +2, ... until the schedule fits.
The hidden test needs a capacity of 200,000 starting from 1, a linear
crawl over the answer space with an O(n) check each step, so it's too slow. The
answer lies between max(weights) and sum(weights), and feasibility is
monotonic in the capacity: find a way to home in on it far faster than one step
at a time.
Starter code
using System;
public class Solution
{
// TODO: return the minimum capacity shipping all packages, in order, within the given days.
public long ShipWithinDays(int[] weights, int days)
{
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
- Binary search on the answer
- Search the space of candidate answers when feasibility is monotonic.
- Greedy algorithms
- Make the locally best choice when an exchange argument proves it stays globally optimal.
Related katas
- Magnetic Force Between Two Balls Hard Free Place m balls in baskets to maximize the smallest gap between any two.
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Cutting Ribbons Medium Free The longest equal piece length that still yields k pieces.