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

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).

Hints

1. Sort jobs by end time so that when you process a job, all potentially compatible earlier jobs are in a prefix.
2. 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.