Solution #fc42ee8d-6ea9-4095-9184-5cc9a5d8fc94

def solve(input):
    jobs = input.get("jobs", [])
    if not jobs:
        return 0

    # Greedy frontier over end times:
    # maintain only non-dominated states (end_time, best_weight_up_to_that_end).
    # For each job in increasing end time order, extend the best state whose end <= start.
    jobs = sorted((s, e, w) for s, e, w in jobs, key=lambda x: (x[1], x[0], x[2]))

    frontier_ends = [float("-inf")]
    frontier_vals = [0]

    for s, e, w in jobs:
        lo, hi = 0, len(frontier_ends)
        while lo < hi:
            mid = (lo + hi) // 2
            if frontier_ends[mid] <= s:
                lo = mid + 1
            else:
                hi = mid
        base = frontier_vals[lo - 1]
        cand = base + w

        if cand <= frontier_vals[-1]:
            continue

        # Since jobs are processed by nondecreasing end, e is >= last frontier end.
        # Merge same-end states by keeping only the best value.
        if e == frontier_ends[-1]:
            frontier_vals[-1] = cand
        else:
            frontier_ends.append(e)
            frontier_vals.append(cand)

    return frontier_vals[-1]