Solution #1f2128e7-a3e8-4e0c-976a-a17cf270ed44

completed

Score

80% (4/5)

Runtime

20μs

Delta

New score

-20.0% vs best

Improved from parent

Solution Lineage

Current80%Improved from parent
92397d700%Regression from parent
7cbd604b80%Improved from parent
fc42ee8d0%Regression from parent
b0db196680%Same as parent
692ab45880%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["jobs"] if isinstance(input, dict) and "jobs" in input else []
    if not jobs:
        return 0

    jobs = sorted(jobs, key=lambda x: x[1])
    n = len(jobs)
    ends = [jobs[i][1] for i in range(n)]

    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        s, e, w = jobs[i - 1]

        lo, hi = 0, i - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if ends[mid] <= s:
                lo = mid + 1
            else:
                hi = mid
        p = lo
        if p > 0 or (i > 1 and ends[0] <= s):
            if p == i - 1 and ends[p] <= s:
                prev_count = p + 1
            elif p < i - 1 or (i > 1 and ends[p] > s):
                prev_count = p
            else:
                prev_count = p
        else:
            prev_count = 0

        take = w + dp[prev_count]
        skip = dp[i - 1]
        dp[i] = take if take > skip else skip

    return dp[n]

Compare with Champion

Score Difference

-20.0%

Runtime Advantage

2μs slower

Code Size

37 vs 39 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 jobs = input["jobs"] if isinstance(input, dict) and "jobs" in input else []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[1])6 return 0
7 n = len(jobs)7
8 ends = [jobs[i][1] for i in range(n)]8 jobs = []
99 for j in raw:
10 dp = [0] * (n + 1)10 if isinstance(j, (list, tuple)) and len(j) == 3:
1111 jobs.append((j[1], j[0], j[2])) # sort by end, store as (end, start, weight)
12 for i in range(1, n + 1):12 if not jobs:
13 s, e, w = jobs[i - 1]13 return 0
1414
15 lo, hi = 0, i - 115 jobs.sort()
16 while lo < hi:16 ends = []
17 mid = (lo + hi) // 217 bests = []
18 if ends[mid] <= s:18
19 lo = mid + 119 for e, s, w in jobs:
20 else:20 lo = 0
21 hi = mid21 hi = len(ends)
22 p = lo22 while lo < hi:
23 if p > 0 or (i > 1 and ends[0] <= s):23 mid = (lo + hi) >> 1
24 if p == i - 1 and ends[p] <= s:24 if ends[mid] <= s:
25 prev_count = p + 125 lo = mid + 1
26 elif p < i - 1 or (i > 1 and ends[p] > s):26 else:
27 prev_count = p27 hi = mid
28 else:28
29 prev_count = p29 candidate = w + (bests[lo - 1] if lo else 0)
30 else:30 current = bests[-1] if bests else 0
31 prev_count = 031
3232 if candidate > current:
33 take = w + dp[prev_count]33 if ends and ends[-1] == e:
34 skip = dp[i - 1]34 bests[-1] = candidate
35 dp[i] = take if take > skip else skip35 else:
3636 ends.append(e)
37 return dp[n]37 bests.append(candidate)
3838
3939 return bests[-1] if bests else 0
Your Solution
80% (4/5)20μs
1def solve(input):
2    jobs = input["jobs"] if isinstance(input, dict) and "jobs" in input else []
3    if not jobs:
4        return 0
5
6    jobs = sorted(jobs, key=lambda x: x[1])
7    n = len(jobs)
8    ends = [jobs[i][1] for i in range(n)]
9
10    dp = [0] * (n + 1)
11
12    for i in range(1, n + 1):
13        s, e, w = jobs[i - 1]
14
15        lo, hi = 0, i - 1
16        while lo < hi:
17            mid = (lo + hi) // 2
18            if ends[mid] <= s:
19                lo = mid + 1
20            else:
21                hi = mid
22        p = lo
23        if p > 0 or (i > 1 and ends[0] <= s):
24            if p == i - 1 and ends[p] <= s:
25                prev_count = p + 1
26            elif p < i - 1 or (i > 1 and ends[p] > s):
27                prev_count = p
28            else:
29                prev_count = p
30        else:
31            prev_count = 0
32
33        take = w + dp[prev_count]
34        skip = dp[i - 1]
35        dp[i] = take if take > skip else skip
36
37    return dp[n]
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