Solution #9db0fb85-2f52-430c-b5d8-101fcf861c93

completed

Score

80% (4/5)

Runtime

31μs

Delta

+100.0% vs parent

-20.0% vs best

Improved from parent

Solution Lineage

Current80%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(jobs, key=lambda x: x[0])
    n = len(jobs)
    starts = [job[0] for job in jobs]

    def find_next(i, lo, hi):
        if lo > hi:
            return lo
        mid = (lo + hi) // 2
        if starts[mid] < jobs[i][1]:
            return find_next(i, mid + 1, hi)
        return find_next(i, lo, mid - 1)

    memo = {}

    def dp(i):
        if i >= n:
            return 0
        if i in memo:
            return memo[i]

        skip = dp(i + 1)
        j = find_next(i, i + 1, n - 1)
        take = jobs[i][2] + dp(j)

        memo[i] = take if take > skip else skip
        return memo[i]

    return dp(0)

Compare with Champion

Score Difference

-20.0%

Runtime Advantage

13μs slower

Code Size

33 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(jobs, key=lambda x: x[0])6 return 0
7 n = len(jobs)7
8 starts = [job[0] for job in jobs]8 jobs = []
99 for j in raw:
10 def find_next(i, lo, hi):10 if isinstance(j, (list, tuple)) and len(j) == 3:
11 if lo > hi:11 jobs.append((j[1], j[0], j[2])) # sort by end, store as (end, start, weight)
12 return lo12 if not jobs:
13 mid = (lo + hi) // 213 return 0
14 if starts[mid] < jobs[i][1]:14
15 return find_next(i, mid + 1, hi)15 jobs.sort()
16 return find_next(i, lo, mid - 1)16 ends = []
1717 bests = []
18 memo = {}18
1919 for e, s, w in jobs:
20 def dp(i):20 lo = 0
21 if i >= n:21 hi = len(ends)
22 return 022 while lo < hi:
23 if i in memo:23 mid = (lo + hi) >> 1
24 return memo[i]24 if ends[mid] <= s:
2525 lo = mid + 1
26 skip = dp(i + 1)26 else:
27 j = find_next(i, i + 1, n - 1)27 hi = mid
28 take = jobs[i][2] + dp(j)28
2929 candidate = w + (bests[lo - 1] if lo else 0)
30 memo[i] = take if take > skip else skip30 current = bests[-1] if bests else 0
31 return memo[i]31
3232 if candidate > current:
33 return dp(0)33 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)31μs
1def solve(input):
2    jobs = input.get("jobs", [])
3    if not jobs:
4        return 0
5
6    jobs = sorted(jobs, key=lambda x: x[0])
7    n = len(jobs)
8    starts = [job[0] for job in jobs]
9
10    def find_next(i, lo, hi):
11        if lo > hi:
12            return lo
13        mid = (lo + hi) // 2
14        if starts[mid] < jobs[i][1]:
15            return find_next(i, mid + 1, hi)
16        return find_next(i, lo, mid - 1)
17
18    memo = {}
19
20    def dp(i):
21        if i >= n:
22            return 0
23        if i in memo:
24            return memo[i]
25
26        skip = dp(i + 1)
27        j = find_next(i, i + 1, n - 1)
28        take = jobs[i][2] + dp(j)
29
30        memo[i] = take if take > skip else skip
31        return memo[i]
32
33    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