Solution #530effa8-4cb6-4512-936a-f185b6871f2d

1def solve(input):
2    if type(input) is not dict:
3        return 0
4    raw = input.get("jobs")
5    if not raw:
6        return 0
7
8    jobs = []
9    starts = []
10    ends = []
11
12    for job in raw:
13        if type(job) is list or type(job) is tuple:
14            if len(job) == 3:
15                s = job[0]
16                e = job[1]
17                w = job[2]
18                jobs.append((s, e, w))
19                starts.append(s)
20                ends.append(e)
21
22    n = len(jobs)
23    if n == 0:
24        return 0
25
26    starts = sorted(set(starts))
27    ends = sorted(set(ends))
28
29    s_rank = {}
30    for i, v in enumerate(starts, 1):
31        s_rank[v] = i
32
33    e_rank = {}
34    for i, v in enumerate(ends, 1):
35        e_rank[v] = i
36
37    size = len(starts)
38    buckets = [[] for _ in range(len(ends) + 1)]
39    for s, e, w in jobs:
40        buckets[e_rank[e]].append((s_rank[s], w))
41
42    bit = [0] * (size + 1)
43
44    for ei in range(1, len(ends) + 1):
45        bucket = buckets[ei]
46        if bucket:
47            prev_end = ends[ei - 2] if ei > 1 else None
48            for sr, w in bucket:
49                s_val = starts[sr - 1]
50                lo = 0
51                hi = ei - 1
52                while lo < hi:
53                    mid = (lo + hi) >> 1
54                    if ends[mid] <= s_val:
55                        lo = mid + 1
56                    else:
57                        hi = mid
58                k = lo
59                q = 0
60                while k:
61                    v = bit[k]
62                    if v > q:
63                        q = v
64                    k &= k - 1
65                val = q + w
66                idx = sr
67                while idx <= size:
68                    if val > bit[idx]:
69                        bit[idx] = val
70                    idx += idx & -idx
71
72    ans = 0
73    i = size
74    while i:
75        v = bit[i]
76        if v > ans:
77            ans = v
78        i &= i - 1
79    return ans

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