Maximize profit from non-overlapping jobs

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.