Solution #692ab458-2805-4554-b61c-a9db15e4163c

completed

Score

80% (4/5)

Runtime

45μs

Delta

No change vs parent

-20.0% vs best

Same as parent

Solution Lineage

Current80%Same as parent
8996709780%Improved from parent
17dd25090%Regression from parent
2524a75f80%Same as parent
e8534c5f80%Same as parent
bc1ec94080%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((tuple(job) for job in jobs), key=lambda x: (x[1], x[0], x[2]))
    ends = [e for _, e, _ in jobs]

    def upper_bound(arr, target):
        lo, hi = 0, len(arr)
        while lo < hi:
            mid = (lo + hi) // 2
            if arr[mid] <= target:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def step(state, job):
        dp, built = state
        s, e, w = job
        i = upper_bound(ends, s)
        best_before = dp[i]
        cur = dp[-1]
        return (dp + [cur if cur > best_before + w else best_before + w], built + 1)

    return __import__("functools").reduce(step, jobs, ([0], 0))[0][-1]

Compare with Champion

Score Difference

-20.0%

Runtime Advantage

27μs slower

Code Size

27 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], x[0], x[2]))6 return 0
7 ends = [e for _, e, _ in jobs]7
88 jobs = []
9 def upper_bound(arr, target):9 for j in raw:
10 lo, hi = 0, len(arr)10 if isinstance(j, (list, tuple)) and len(j) == 3:
11 while lo < hi:11 jobs.append((j[1], j[0], j[2])) # sort by end, store as (end, start, weight)
12 mid = (lo + hi) // 212 if not jobs:
13 if arr[mid] <= target:13 return 0
14 lo = mid + 114
15 else:15 jobs.sort()
16 hi = mid16 ends = []
17 return lo17 bests = []
1818
19 def step(state, job):19 for e, s, w in jobs:
20 dp, built = state20 lo = 0
21 s, e, w = job21 hi = len(ends)
22 i = upper_bound(ends, s)22 while lo < hi:
23 best_before = dp[i]23 mid = (lo + hi) >> 1
24 cur = dp[-1]24 if ends[mid] <= s:
25 return (dp + [cur if cur > best_before + w else best_before + w], built + 1)25 lo = mid + 1
2626 else:
27 return __import__("functools").reduce(step, jobs, ([0], 0))[0][-1]27 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)45μ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], x[0], x[2]))
7    ends = [e for _, e, _ in jobs]
8
9    def upper_bound(arr, target):
10        lo, hi = 0, len(arr)
11        while lo < hi:
12            mid = (lo + hi) // 2
13            if arr[mid] <= target:
14                lo = mid + 1
15            else:
16                hi = mid
17        return lo
18
19    def step(state, job):
20        dp, built = state
21        s, e, w = job
22        i = upper_bound(ends, s)
23        best_before = dp[i]
24        cur = dp[-1]
25        return (dp + [cur if cur > best_before + w else best_before + w], built + 1)
26
27    return __import__("functools").reduce(step, jobs, ([0], 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