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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Maximize reward by scheduling jobs | Airbnb Coding Question

Quick Overview

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.

Maximize reward by scheduling jobs

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

You are given an array `jobs` where `jobs[i] = (start_i, end_i, reward_i)`. Choose a subset of jobs with maximum total reward such that no two chosen jobs overlap. Treat each job as a half-open interval `[start_i, end_i)`, so a job ending at time `t` does not overlap a job starting at time `t`. Zero-length jobs with `start_i == end_i` are allowed. Return both the maximum reward and one optimal set of original 0-based job indices in the order they are scheduled. If multiple optimal answers exist, you may return any one of them. Your solution should aim for `O(n log n)` time.

Constraints

`0 <= n <= 100000`
`jobs[i] = (start_i, end_i, reward_i)`
`-2^63 <= start_i, end_i <= 2^63 - 1`
`start_i <= end_i`
`0 <= reward_i <= 10^9`

Examples

Input: ([],)

Expected Output: (0, [])

Explanation: There are no jobs to take, so the maximum reward is 0 and the chosen index list is empty.

Input: ([(2, 5, 10)],)

Expected Output: (10, [0])

Explanation: With only one job, the best choice is to take it.

Input: ([(1, 3, 50), (3, 5, 20), (6, 19, 100), (2, 100, 200)],)

Expected Output: (200, [3])

Explanation: Taking job 3 alone yields reward 200, which is better than taking jobs 0, 1, and 2 for a total of 170.

Input: ([(1, 1, 5), (1, 2, 4), (2, 2, 3), (2, 3, 6)],)

Expected Output: (18, [0, 1, 2, 3])

Explanation: Under half-open interval rules, jobs that touch at endpoints do not overlap, and zero-length jobs can be included as well.

Input: ([(1, 4, 5), (1, 4, 7), (4, 6, 4), (6, 7, 3)],)

Expected Output: (14, [1, 2, 3])

Explanation: Jobs 0 and 1 overlap completely, so choose the more rewarding one (job 1), then chain jobs 2 and 3.

Hints

Sort jobs by end time so that when you process a job, all potentially compatible earlier jobs are in a prefix.
For each job, use binary search to find the last job whose end time is less than or equal to the current job's start time, then use dynamic programming to choose between taking or skipping the job.

Quick Overview