Solution #ec24a221-7ffc-4e1d-b91b-564783432de8

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[0], j[1], j[2]))
12
13    if not jobs:
14        return 0
15
16    jobs.sort(key=lambda x: x[1])
17
18    ends = [e for _, e, _ in jobs]
19
20    def upper_bound(arr, x, hi):
21        lo = 0
22        while lo < hi:
23            mid = (lo + hi) >> 1
24            if arr[mid] <= x:
25                lo = mid + 1
26            else:
27                hi = mid
28        return lo
29
30    n = len(jobs)
31
32    def dc(l, r):
33        if l > r:
34            return [0]
35        if l == r:
36            s, e, w = jobs[l]
37            return [0, w if w > 0 else 0]
38
39        m = (l + r) >> 1
40        left_dp = dc(l, m)
41        right_dp = dc(m + 1, r)
42
43        left_len = m - l + 1
44        right_len = r - m
45
46        res = [0] * (left_len + right_len + 1)
47
48        i = 0
49        while i <= left_len:
50            res[i] = left_dp[i]
51            i += 1
52
53        j = 1
54        while j <= right_len:
55            v = right_dp[j]
56            if v > res[left_len + j]:
57                res[left_len + j] = v
58            j += 1
59
60        j = m + 1
61        while j <= r:
62            s, e, w = jobs[j]
63            p = upper_bound(ends, s, m + 1) - l
64            val = left_dp[p] + w
65            idx = left_len + (j - m)
66            if val > res[idx]:
67                res[idx] = val
68            j += 1
69
70        i = 1
71        total = left_len + right_len
72        while i <= total:
73            if res[i - 1] > res[i]:
74                res[i] = res[i - 1]
75            i += 1
76
77        return res
78
79    ans = dc(0, n - 1)[n]
80    return ans if ans > 0 else 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