Solution #ae983b24-e8a7-45f9-8429-44008f15a090

completed

Score

80% (4/5)

Runtime

40μs

Delta

No change vs parent

-20.0% vs best

Same as parent

Solution Lineage

Current80%Same as parent
8252644380%Same as parent
9db0fb8580%Improved from parent
df1d6fd340%Regression from parent
ae833bc280%Same as parent
c90b917a80%First in chain

Code

def solve(input):
    jobs = input.get("jobs", [])
    if not jobs:
        return 0

    jobs = sorted((tuple(job) for job in jobs), key=lambda x: x[1])
    ends = [e for _, e, _ in jobs]

    def upper_bound(arr, x, lo=0, hi=None):
        hi = len(arr) if hi is None else hi
        return lo if lo >= hi else (
            upper_bound(arr, x, (lo + hi) // 2 + 1, hi)
            if arr[(lo + hi) // 2] <= x
            else upper_bound(arr, x, lo, (lo + hi) // 2)
        )

    def build(i, dp):
        return dp if i == len(jobs) else build(
            i + 1,
            dp + [max(dp[-1], jobs[i][2] + dp[upper_bound(ends, jobs[i][0], 0, i)])]
        )

    return build(0, [0])[-1]

Compare with Champion

Score Difference

-20.0%

Runtime Advantage

22μs slower

Code Size

23 vs 39 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 jobs = input.get("jobs", [])2 if not isinstance(input, dict):
3 if not jobs:3 return 0
4 return 04 raw = input.get("jobs")
55 if not raw:
6 jobs = sorted((tuple(job) for job in jobs), key=lambda x: x[1])6 return 0
7 ends = [e for _, e, _ in jobs]7
88 jobs = []
9 def upper_bound(arr, x, lo=0, hi=None):9 for j in raw:
10 hi = len(arr) if hi is None else hi10 if isinstance(j, (list, tuple)) and len(j) == 3:
11 return lo if lo >= hi else (11 jobs.append((j[1], j[0], j[2])) # sort by end, store as (end, start, weight)
12 upper_bound(arr, x, (lo + hi) // 2 + 1, hi)12 if not jobs:
13 if arr[(lo + hi) // 2] <= x13 return 0
14 else upper_bound(arr, x, lo, (lo + hi) // 2)14
15 )15 jobs.sort()
1616 ends = []
17 def build(i, dp):17 bests = []
18 return dp if i == len(jobs) else build(18
19 i + 1,19 for e, s, w in jobs:
20 dp + [max(dp[-1], jobs[i][2] + dp[upper_bound(ends, jobs[i][0], 0, i)])]20 lo = 0
21 )21 hi = len(ends)
2222 while lo < hi:
23 return build(0, [0])[-1]23 mid = (lo + hi) >> 1
2424 if ends[mid] <= s:
2525 lo = mid + 1
2626 else:
2727 hi = mid
2828
2929 candidate = w + (bests[lo - 1] if lo else 0)
3030 current = bests[-1] if bests else 0
3131
3232 if candidate > current:
3333 if ends and ends[-1] == e:
3434 bests[-1] = candidate
3535 else:
3636 ends.append(e)
3737 bests.append(candidate)
3838
3939 return bests[-1] if bests else 0
Your Solution
80% (4/5)40μs
1def solve(input):
2    jobs = input.get("jobs", [])
3    if not jobs:
4        return 0
5
6    jobs = sorted((tuple(job) for job in jobs), key=lambda x: x[1])
7    ends = [e for _, e, _ in jobs]
8
9    def upper_bound(arr, x, lo=0, hi=None):
10        hi = len(arr) if hi is None else hi
11        return lo if lo >= hi else (
12            upper_bound(arr, x, (lo + hi) // 2 + 1, hi)
13            if arr[(lo + hi) // 2] <= x
14            else upper_bound(arr, x, lo, (lo + hi) // 2)
15        )
16
17    def build(i, dp):
18        return dp if i == len(jobs) else build(
19            i + 1,
20            dp + [max(dp[-1], jobs[i][2] + dp[upper_bound(ends, jobs[i][0], 0, i)])]
21        )
22
23    return build(0, [0])[-1]
Champion
100% (5/5)18μs
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