Solution #7cbd604b-f218-4e16-8eed-b65017e809b8

1def solve(input):
2    jobs = input.get("jobs", [])
3    if not jobs:
4        return 0
5
6    # Recursive weighted interval scheduling:
7    # sort by start time, then for each job choose skip/take.
8    # If taking a job, jump to the first job with start >= current end.
9    jobs = sorted((s, e, w) for s, e, w in jobs)
10    n = len(jobs)
11    starts = [s for s, _, _ in jobs]
12
13    next_idx = [n] * n
14    for i in range(n):
15        end_i = jobs[i][1]
16        lo, hi = i + 1, n
17        while lo < hi:
18            mid = (lo + hi) // 2
19            if starts[mid] < end_i:
20                lo = mid + 1
21            else:
22                hi = mid
23        next_idx[i] = lo
24
25    memo = {}
26
27    def dp(i):
28        if i >= n:
29            return 0
30        if i in memo:
31            return memo[i]
32        skip = dp(i + 1)
33        take = jobs[i][2] + dp(next_idx[i])
34        ans = take if take > skip else skip
35        memo[i] = ans
36        return ans
37
38    return dp(0)

1def solve(input):
2    if not isinstance(input, dict):
3        return 0
4    raw = input.get("jobs")
5    if not raw:
6        return 0
7
8    jobs = []
9    for j in raw:
10        if isinstance(j, (list, tuple)) and len(j) == 3:
11            jobs.append((j[1], j[0], j[2]))  # sort by end, store as (end, start, weight)
12    if not jobs:
13        return 0
14
15    jobs.sort()
16    ends = []
17    bests = []
18
19    for e, s, w in jobs:
20        lo = 0
21        hi = len(ends)
22        while lo < hi:
23            mid = (lo + hi) >> 1
24            if ends[mid] <= s:
25                lo = mid + 1
26            else:
27                hi = mid
28
29        candidate = w + (bests[lo - 1] if lo else 0)
30        current = bests[-1] if bests else 0
31
32        if candidate > current:
33            if ends and ends[-1] == e:
34                bests[-1] = candidate
35            else:
36                ends.append(e)
37                bests.append(candidate)
38
39    return bests[-1] if bests else 0