Solution #ae833bc2-964c-4bae-819b-3c320632333a

completed

Score

80% (4/5)

Runtime

22μs

Delta

No change vs parent

-20.0% vs best

Same as parent

Solution Lineage

Current80%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[1])
    ends = [job[1] for job in jobs]
    n = len(jobs)

    dp = [0] * (n + 1)

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

        lo, hi = 0, i - 2
        ans = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if ends[mid] <= s:
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1

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

    return dp[n]

Compare with Champion

Score Difference

-20.0%

Runtime Advantage

4μs slower

Code Size

29 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[1])6 return 0
7 ends = [job[1] for job in jobs]7
8 n = len(jobs)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 - 215 jobs.sort()
16 ans = -116 ends = []
17 while lo <= hi:17 bests = []
18 mid = (lo + hi) // 218
19 if ends[mid] <= s:19 for e, s, w in jobs:
20 ans = mid20 lo = 0
21 lo = mid + 121 hi = len(ends)
22 else:22 while lo < hi:
23 hi = mid - 123 mid = (lo + hi) >> 1
2424 if ends[mid] <= s:
25 take = w + dp[ans + 1]25 lo = mid + 1
26 skip = dp[i - 1]26 else:
27 dp[i] = take if take > skip else skip27 hi = mid
2828
29 return dp[n]29 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)22μ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[1])
7    ends = [job[1] for job in jobs]
8    n = len(jobs)
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 - 2
16        ans = -1
17        while lo <= hi:
18            mid = (lo + hi) // 2
19            if ends[mid] <= s:
20                ans = mid
21                lo = mid + 1
22            else:
23                hi = mid - 1
24
25        take = w + dp[ans + 1]
26        skip = dp[i - 1]
27        dp[i] = take if take > skip else skip
28
29    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