Non-Overlapping Gigs — Solution & Editorial

Back to the Problem

Sort jobs by end time; dp keyed by end time = max(skip this job, take it + best profit of jobs ending ≤ its start). Binary search for the compatible predecessor.

Complexity: O(N log N)