Solution #41f00984-0a11-4e61-8f6d-d1a04b53429c

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    starts = []
10    ends = []
11    for j in raw:
12        if isinstance(j, (list, tuple)) and len(j) == 3:
13            s, e, w = j[0], j[1], j[2]
14            jobs.append((s, e, w))
15            starts.append(s)
16            ends.append(e)
17
18    if not jobs:
19        return 0
20
21    times = sorted(set(starts + ends))
22    m = len(times)
23
24    index = {}
25    for i, t in enumerate(times):
26        index[t] = i
27
28    best_start = [0] * m
29    for i, t in enumerate(times):
30        if t in index:
31            best_start[i] = index[t]
32
33    prefix_lookup = [0] * m
34    if m:
35        prefix_lookup[0] = 0
36        for i in range(1, m):
37            prefix_lookup[i] = i - 1
38
39    by_end = [[] for _ in range(m)]
40    for s, e, w in jobs:
41        by_end[index[e]].append((index[s], w))
42
43    dp = [0] * m
44    for ei in range(m):
45        best = dp[ei - 1] if ei else 0
46        bucket = by_end[ei]
47        for si, w in bucket:
48            prev = dp[prefix_lookup[si]] if si > 0 else 0
49            cand = prev + w
50            if cand > best:
51                best = cand
52        dp[ei] = best
53
54    return dp[-1] if dp 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