Solution #3ae05058-ce9b-4653-b7af-94a7ed663ee4

1def solve(input):
2    jobs = input.get("jobs", []) if isinstance(input, dict) else []
3
4    def normalize(i):
5        if i >= len(jobs):
6            return []
7        job = jobs[i]
8        rest = normalize(i + 1)
9        if isinstance(job, (list, tuple)) and len(job) == 3:
10            return [(job[0], job[1], job[2])] + rest
11        return rest
12
13    arr = normalize(0)
14    if not arr:
15        return 0
16
17    def sort_by_end(a):
18        n = len(a)
19        if n <= 1:
20            return a
21        mid = n // 2
22        left = sort_by_end(a[:mid])
23        right = sort_by_end(a[mid:])
24
25        def merge(i, j):
26            if i >= len(left):
27                return right[j:]
28            if j >= len(right):
29                return left[i:]
30            le = left[i]
31            ri = right[j]
32            if le[1] < ri[1] or (le[1] == ri[1] and le[0] <= ri[0]):
33                return [le] + merge(i + 1, j)
34            return [ri] + merge(i, j + 1)
35
36        return merge(0, 0)
37
38    arr = sort_by_end(arr)
39    n = len(arr)
40
41    def build_ends(i):
42        if i >= n:
43            return []
44        return [arr[i][1]] + build_ends(i + 1)
45
46    ends = build_ends(0)
47
48    def upper_bound(x, lo, hi):
49        if lo >= hi:
50            return lo
51        mid = (lo + hi) // 2
52        if ends[mid] <= x:
53            return upper_bound(x, mid + 1, hi)
54        return upper_bound(x, lo, mid)
55
56    memo = {}
57
58    def dp(i):
59        if i < 0:
60            return 0
61        if i in memo:
62            return memo[i]
63        s, e, w = arr[i]
64        p = upper_bound(s, 0, i) - 1
65        take = w + dp(p)
66        skip = dp(i - 1)
67        ans = take if take > skip else skip
68        memo[i] = ans
69        return ans
70
71    return dp(n - 1)

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