Most Workshops Before Deadlines

HardGreedy

Problem

A trainer can attend one workshop at a time, back to back, starting on day 0. Workshop i is [duration, lastDay]: it takes duration consecutive days and must be finished by day lastDay (finishing exactly on lastDay is fine).

Return the largest number of workshops the trainer can complete.

Example 1

Input:
workshops = [[3, 5], [4, 6], [2, 7], [5, 9]]
Output:
2

For example [3, 5] (days 0–3) and [2, 7] (days 3–5). No three fit their deadlines.

Example 2

Input:
workshops = [[1, 2]]
Output:
1

Example 3

Input:
workshops = [[3, 2], [4, 3]]
Output:
0

Neither can finish in time even alone.

Constraints

  • 1 ≤ workshops.length ≤ 10^4
  • 1 ≤ duration, lastDay ≤ 10^4

Hint

Show the first hint

For a fixed set of workshops, in which order should you take them to have the best chance of meeting every deadline?

Walkthrough

How to approach it

01Clarify before coding

  • Must workshops run back to back with no gaps? Gaps never help, so assume back to back from day 0.
  • Is finishing exactly on lastDay allowed? Yes.
  • Can a workshop with duration > lastDay ever be taken? No.

02Brute force

Try every subset, sort it by deadline and check feasibility; keep the largest feasible subset.

Cost: O(2^n · n log n): impossible for 10^4 workshops. A DP over (index, time) is O(n · maxDay) = 10^8, borderline.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.