Solution #2baa50c1-9c81-46b8-8af0-08d964c9e270

1def solve(input):
2    jobs = input.get("jobs", []) if isinstance(input, dict) else []
3    if not jobs:
4        return 0
5
6    def build(i, acc):
7        if i >= len(jobs):
8            return acc
9        job = jobs[i]
10        if isinstance(job, (list, tuple)) and len(job) == 3:
11            return build(i + 1, acc + [tuple(job)])
12        return build(i + 1, acc)
13
14    arr = build(0, [])
15    if not arr:
16        return 0
17
18    def merge(a, b, key):
19        if not a:
20            return b
21        if not b:
22            return a
23        if key(a[0]) <= key(b[0]):
24            return [a[0]] + merge(a[1:], b, key)
25        return [b[0]] + merge(a, b[1:], key)
26
27    def mergesort(a, key):
28        n = len(a)
29        if n <= 1:
30            return a
31        mid = n // 2
32        return merge(mergesort(a[:mid], key), mergesort(a[mid:], key), key)
33
34    arr = mergesort(arr, lambda x: x[0])
35    n = len(arr)
36
37    starts = list(map(lambda x: x[0], arr))
38
39    def lower_bound(x, lo, hi):
40        if lo >= hi:
41            return lo
42        mid = (lo + hi) // 2
43        if starts[mid] < x:
44            return lower_bound(x, mid + 1, hi)
45        return lower_bound(x, lo, mid)
46
47    memo = {}
48
49    def dp(i):
50        if i >= n:
51            return 0
52        if i in memo:
53            return memo[i]
54        s, e, w = arr[i]
55        j = lower_bound(e, i + 1, n)
56        take = w + dp(j)
57        skip = dp(i + 1)
58        memo[i] = take if take > skip else skip
59        return memo[i]
60
61    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