Solution #17dd2509-2ccd-4963-a4e2-50b7d785ac1a

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

    # Greedy frontier over end times:
    # keep only Pareto-optimal states (end_time, best_weight).
    # For each job in increasing end time, 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

        if e > frontier_ends[-1]:
            frontier_ends.append(e)
            frontier_vals.append(cand)
        else:
            lo, hi = 0, len(frontier_ends)
            while lo < hi:
                mid = (lo + hi) // 2
                if frontier_ends[mid] < e:
                    lo = mid + 1
                else:
                    hi = mid
            pos = lo
            if cand > frontier_vals[pos]:
                frontier_ends[pos] = e
                frontier_vals[pos] = cand
                i = pos + 1
                while i < len(frontier_vals) and frontier_vals[i] <= cand:
                    del frontier_vals[i]
                    del frontier_ends[i]

    return frontier_vals[-1]