Maximize reward by scheduling jobs

Q: Maximize reward by scheduling jobs

This question evaluates understanding of weighted interval scheduling, dynamic programming, and efficient algorithm design for large-scale inputs, as well as reasoning about correctness, complexity, and edge cases like identical times or zero-length jobs.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Airbnb.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Question

Given n jobs, each with a start time, end time, and reward, choose a subset of non-overlapping jobs to maximize total reward. Return the maximum reward and one optimal set of job indices. Constraints: n up to 100,000; times within 32-bit or 64-bit integers; rewards non-negative. Aim for O(n log n) time and near O(n) space. Explain your algorithm (e.g., sorting, binary search, and DP), prove correctness, analyze complexity, and discuss edge cases such as identical start/end times and zero-length jobs.

PracHub · Accepted Answer

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)

Quick Overview

Solution

Hints

Quick Overview