Solution
def solution(jobs):
"""
Weighted interval scheduling in O(n log n) time.
Algorithm:
1. Attach original indices to each job and sort by end time.
2. For each sorted job i, binary-search the last earlier job p[i]
whose end time is <= the current job's start time.
3. Let dp[i] be the maximum reward obtainable using the first i sorted jobs.
Then the recurrence is:
dp[i] = max(dp[i - 1], reward_i + dp[p[i]])
because an optimal solution on the first i jobs either skips job i,
or takes it and combines it with the best compatible prefix.
4. Record which jobs were taken and backtrack to reconstruct one optimal
set of original indices.
Correctness sketch:
After sorting by end time, every job compatible with sorted job i lies in
the prefix ending at p[i]. Any optimal solution among the first i jobs must
be in exactly one of two cases:
- it excludes job i, giving value dp[i - 1], or
- it includes job i, in which case the remaining chosen jobs must form an
optimal solution among the first p[i] jobs, giving
reward_i + dp[p[i]].
Taking the maximum of these two values therefore yields the optimal value
for the first i jobs. By induction over i, dp[n] is optimal for all jobs.
The backtracking step follows the same decisions, so it reconstructs a
schedule whose reward is exactly dp[n].
Edge cases handled:
- Empty input returns (0, []).
- Identical start/end times are handled naturally by sorting and binary search.
- Zero-length jobs (start == end) are valid. Because intervals are treated
as [start, end), jobs with end == next_start are compatible, including
multiple zero-length jobs at the same time.
"""
from bisect import bisect_right
n = len(jobs)
if n == 0:
return (0, [])
ordered = [(start, end, reward, idx) for idx, (start, end, reward) in enumerate(jobs)]
ordered.sort(key=lambda job: (job[1], job[0], job[3]))
ends = [job[1] for job in ordered]
# p[i] = number of jobs in the sorted prefix that end <= start time of job i
# Using 1-based DP indexing, this is exactly the DP state we should jump to.
p = [0] * (n + 1)
for i, (start, end, reward, idx) in enumerate(ordered, 1):
p[i] = bisect_right(ends, start, 0, i - 1)
dp = [0] * (n + 1)
take = [False] * (n + 1)
for i in range(1, n + 1):
reward = ordered[i - 1][2]
include = reward + dp[p[i]]
exclude = dp[i - 1]
if include > exclude:
dp[i] = include
take[i] = True
else:
dp[i] = exclude
chosen = []
i = n
while i > 0:
if take[i]:
chosen.append(ordered[i - 1][3])
i = p[i]
else:
i -= 1
chosen.reverse()
return (dp[n], chosen)
Time complexity: O(n log n). Space complexity: O(n).