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 Onsite 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 profit from non-overlapping jobs

Quick Overview

This question evaluates proficiency in weighted interval scheduling, dynamic programming concepts, and the use of efficient data structures for large-scale scheduling problems, including handling duplicate times, large reward values, and memory constraints.

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given up to N = 200,000 jobs; each job i has a start time s_i, end time e_i (s_i < e_i), and reward w_i. Select a subset of non-overlapping jobs to maximize total reward. Return the maximum reward and one optimal set of job indices. Design an O(N log N) algorithm using sorting plus binary search or a balanced tree; explain how you reconstruct the chosen jobs and analyze time/space complexity. Handle duplicate start/end times, large rewards (up to 1e 9), and memory limits. Discuss alternatives (e.g., segment tree, coordinate compression) and how you would adapt the approach if jobs arrive online.

Quick Answer: This question evaluates proficiency in weighted interval scheduling, dynamic programming concepts, and the use of efficient data structures for large-scale scheduling problems, including handling duplicate times, large reward values, and memory constraints.

You are given a list of jobs, where jobs[i] = (s_i, e_i, w_i) contains a start time, end time, and reward. Two jobs are compatible if the earlier job ends at or before the later job starts. Choose a subset of pairwise non-overlapping jobs that maximizes total reward. Return a tuple (max_reward, chosen_indices), where chosen_indices contains the original 0-based indices of one optimal subset in the order the jobs are performed. Your algorithm should run in O(N log N) for up to 200,000 jobs. Duplicate start/end times are allowed, rewards can be large, and you should reconstruct the chosen jobs efficiently. If the input is empty, return (0, []). For deterministic output, sort jobs by (end, start, index). During dynamic programming, if taking the current job gives the same total reward as skipping it, prefer skipping it. In an interview explanation, be prepared to describe how you reconstruct the answer, why the complexity is O(N log N), what a segment-tree/coordinate-compression alternative looks like, and how an online version would use an ordered map or balanced tree.

Constraints

0 <= len(jobs) <= 200000
0 <= start < end <= 10^9 for every job
1 <= reward <= 10^9 for every job
The total reward may exceed 32-bit signed integer range

Examples

Input: ([],)

Expected Output: (0, [])

Explanation: With no jobs, the maximum reward is 0 and the chosen set is empty.

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

Expected Output: (200, [3])

Explanation: Taking job 3 alone gives reward 200, which is better than chaining jobs 0, 1, and 2 for 170.

Input: ([(1, 3, 20), (1, 3, 30), (3, 5, 25), (3, 6, 50), (5, 6, 30)],)

Expected Output: (85, [1, 2, 4])

Explanation: Jobs 1, 2, and 4 do not overlap and give 30 + 25 + 30 = 85, which is optimal.

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

Expected Output: (10, [2])

Explanation: Both [0, 1] and [2] give reward 10. After sorting by (end, start, index) and preferring skip on ties, the deterministic answer is [2].

Input: ([(4, 6, 5), (1, 3, 5), (2, 5, 6), (6, 7, 4), (5, 8, 11), (7, 9, 2)],)

Expected Output: (17, [2, 4])

Explanation: Job 2 followed by job 4 gives 6 + 11 = 17, which beats all other compatible subsets.

Input: ([(1, 2, 1000000000), (2, 4, 1000000000), (1, 4, 1999999999), (4, 5, 1)],)

Expected Output: (2000000001, [0, 1, 3])

Explanation: This checks large rewards: jobs 0, 1, and 3 chain together for 2,000,000,001, which is better than taking job 2 plus job 3.

Solution

def solution(jobs):
    from bisect import bisect_right

    n = len(jobs)
    if n == 0:
        return (0, [])

    ordered = [(s, e, w, i) for i, (s, e, w) in enumerate(jobs)]
    ordered.sort(key=lambda job: (job[1], job[0], job[3]))
    ends = [job[1] for job in ordered]

    dp = [0] * (n + 1)
    prev = [0] * (n + 1)
    take = [False] * (n + 1)

    for i in range(1, n + 1):
        s, e, w, idx = ordered[i - 1]
        p = bisect_right(ends, s, 0, i - 1)
        prev[i] = p

        gain_if_take = w + dp[p]
        gain_if_skip = dp[i - 1]

        if gain_if_take > gain_if_skip:
            dp[i] = gain_if_take
            take[i] = True
        else:
            dp[i] = gain_if_skip

    chosen = []
    i = n
    while i > 0:
        if take[i]:
            chosen.append(ordered[i - 1][3])
            i = prev[i]
        else:
            i -= 1

    chosen.reverse()
    return (dp[n], chosen)

Time complexity: O(N log N). Space complexity: O(N).

Hints

After sorting by end time, let dp[i] be the best reward using the first i sorted jobs. For the i-th job, binary search the last job whose end time is <= its start time.
Store both the compatible predecessor position and whether job i was taken. That lets you backtrack one optimal set of original indices. A segment tree with coordinate compression is an alternative O(N log N) approach; an online variant would need an ordered map or balanced tree keyed by end time.

Quick Overview