Solution #bc1ec940-7a9e-4712-9068-6b3704468b2a

completed

Score

80% (4/5)

Runtime

56μs

Delta

No change vs parent

-20.0% vs best

Same as parent

Solution Lineage

Current80%Same as parent
7630bd9e80%Same as parent
ae983b2480%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((s, e, w) for s, e, w in jobs)
    n = len(jobs)
    starts = [jobs[i][0] for i in range(n)]

    next_idx = [n] * n
    for i in range(n):
        target = jobs[i][1]
        lo, hi = i + 1, n
        while lo < hi:
            mid = (lo + hi) // 2
            if starts[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        next_idx[i] = lo

    dp = [0] * (n + 1)
    stack = [(0, 0)]  # (state, index): 0=enter, 1=compute

    while stack:
        state, i = stack.pop()
        if i >= n:
            continue
        if state == 0:
            stack.append((1, i))
            stack.append((0, next_idx[i]))
            stack.append((0, i + 1))
        else:
            take = jobs[i][2] + dp[next_idx[i]]
            skip = dp[i + 1]
            dp[i] = take if take > skip else skip

    return dp[0]

Compare with Champion

Score Difference

-20.0%

Runtime Advantage

38μs slower

Code Size

38 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((s, e, w) for s, e, w in jobs)6 return 0
7 n = len(jobs)7
8 starts = [jobs[i][0] for i in range(n)]8 jobs = []
99 for j in raw:
10 next_idx = [n] * n10 if isinstance(j, (list, tuple)) and len(j) == 3:
11 for i in range(n):11 jobs.append((j[1], j[0], j[2])) # sort by end, store as (end, start, weight)
12 target = jobs[i][1]12 if not jobs:
13 lo, hi = i + 1, n13 return 0
14 while lo < hi:14
15 mid = (lo + hi) // 215 jobs.sort()
16 if starts[mid] < target:16 ends = []
17 lo = mid + 117 bests = []
18 else:18
19 hi = mid19 for e, s, w in jobs:
20 next_idx[i] = lo20 lo = 0
2121 hi = len(ends)
22 dp = [0] * (n + 1)22 while lo < hi:
23 stack = [(0, 0)] # (state, index): 0=enter, 1=compute23 mid = (lo + hi) >> 1
2424 if ends[mid] <= s:
25 while stack:25 lo = mid + 1
26 state, i = stack.pop()26 else:
27 if i >= n:27 hi = mid
28 continue28
29 if state == 0:29 candidate = w + (bests[lo - 1] if lo else 0)
30 stack.append((1, i))30 current = bests[-1] if bests else 0
31 stack.append((0, next_idx[i]))31
32 stack.append((0, i + 1))32 if candidate > current:
33 else:33 if ends and ends[-1] == e:
34 take = jobs[i][2] + dp[next_idx[i]]34 bests[-1] = candidate
35 skip = dp[i + 1]35 else:
36 dp[i] = take if take > skip else skip36 ends.append(e)
3737 bests.append(candidate)
38 return dp[0]38
3939 return bests[-1] if bests else 0
Your Solution
80% (4/5)56μs
1def solve(input):
2    jobs = input.get("jobs", [])
3    if not jobs:
4        return 0
5
6    jobs = sorted((s, e, w) for s, e, w in jobs)
7    n = len(jobs)
8    starts = [jobs[i][0] for i in range(n)]
9
10    next_idx = [n] * n
11    for i in range(n):
12        target = jobs[i][1]
13        lo, hi = i + 1, n
14        while lo < hi:
15            mid = (lo + hi) // 2
16            if starts[mid] < target:
17                lo = mid + 1
18            else:
19                hi = mid
20        next_idx[i] = lo
21
22    dp = [0] * (n + 1)
23    stack = [(0, 0)]  # (state, index): 0=enter, 1=compute
24
25    while stack:
26        state, i = stack.pop()
27        if i >= n:
28            continue
29        if state == 0:
30            stack.append((1, i))
31            stack.append((0, next_idx[i]))
32            stack.append((0, i + 1))
33        else:
34            take = jobs[i][2] + dp[next_idx[i]]
35            skip = dp[i + 1]
36            dp[i] = take if take > skip else skip
37
38    return dp[0]
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