Solution #dbb1f886-015b-4878-acf9-7164e9aea724

completed

Score

20% (1/5)

Runtime

21μs

Delta

-80.0% vs parent

-80.0% vs best

Regression from parent

Solution Lineage

Current20%Regression from parent
1c204190100%Same as parent
37d6e851100%Same as parent
58b73178100%Same as parent
66b5ba20100%Same as parent
6773a310100%Improved from parent
530effa860%Regression from parent
5bd2ddd7100%Same as parent
eef58d00100%Improved from parent
0c1780d720%Regression from parent
2db3327f100%Improved from parent
3ae0505880%Same as parent
2baa50c180%Same as parent
ce0d4fdb80%Same as parent
ad9ca75f80%Same as parent
3277469d80%Improved from parent
f050941640%Regression from parent
8ec5143380%Same as parent
da62d7c880%Same as parent
3d4c689e80%Same as parent
1f2128e780%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):
    if not isinstance(input, dict):
        return 0
    raw = input.get("jobs")
    if not raw:
        return 0

    jobs = []
    for j in raw:
        if isinstance(j, (list, tuple)) and len(j) == 3:
            jobs.append((j[0], j[1], j[2]))
    if not jobs:
        return 0

    jobs.sort(key=lambda x: x[1])
    n = len(jobs)

    ends = [0] * n
    dp = [0] * (n + 1)

    i = 0
    while i < n:
        ends[i] = jobs[i][1]
        i += 1

    i = 1
    while i <= n:
        s, e, w = jobs[i - 1]

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

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

    return dp[n]

Compare with Champion

Score Difference

-80.0%

Runtime Advantage

3μs slower

Code Size

55 vs 39 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 if not isinstance(input, dict):2 if not isinstance(input, dict):
3 return 03 return 0
4 raw = input.get("jobs")4 raw = input.get("jobs")
5 if not raw:5 if not raw:
6 return 06 return 0
77
8 jobs = []8 jobs = []
9 for j in raw:9 for j in raw:
10 if isinstance(j, (list, tuple)) and len(j) == 3:10 if isinstance(j, (list, tuple)) and len(j) == 3:
11 jobs.append((j[0], j[1], j[2]))11 jobs.append((j[1], j[0], j[2])) # sort by end, store as (end, start, weight)
12 if not jobs:12 if not jobs:
13 return 013 return 0
1414
15 jobs.sort(key=lambda x: x[1])15 jobs.sort()
16 n = len(jobs)16 ends = []
1717 bests = []
18 ends = [0] * n18
19 dp = [0] * (n + 1)19 for e, s, w in jobs:
2020 lo = 0
21 i = 021 hi = len(ends)
22 while i < n:22 while lo < hi:
23 ends[i] = jobs[i][1]23 mid = (lo + hi) >> 1
24 i += 124 if ends[mid] <= s:
2525 lo = mid + 1
26 i = 126 else:
27 while i <= n:27 hi = mid
28 s, e, w = jobs[i - 1]28
2929 candidate = w + (bests[lo - 1] if lo else 0)
30 lo = 030 current = bests[-1] if bests else 0
31 hi = i - 131
32 while lo < hi:32 if candidate > current:
33 mid = (lo + hi) >> 133 if ends and ends[-1] == e:
34 if ends[mid] <= s:34 bests[-1] = candidate
35 lo = mid + 135 else:
36 else:36 ends.append(e)
37 hi = mid37 bests.append(candidate)
38 p = lo38
39 if p > 0 and ends[p - 1] > s:39 return bests[-1] if bests else 0
40 p -= 140
41 while p < i - 1 and ends[p] <= s:41
42 p += 142
43 if p == i - 1 and ends[p] <= s:43
44 prev = i - 144
45 elif p >= 0 and ends[p] <= s:45
46 prev = p + 146
47 else:47
48 prev = 048
4949
50 take = dp[prev] + w50
51 skip = dp[i - 1]51
52 dp[i] = take if take > skip else skip52
53 i += 153
5454
55 return dp[n]55
Your Solution
20% (1/5)21μ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[0], j[1], j[2]))
12    if not jobs:
13        return 0
14
15    jobs.sort(key=lambda x: x[1])
16    n = len(jobs)
17
18    ends = [0] * n
19    dp = [0] * (n + 1)
20
21    i = 0
22    while i < n:
23        ends[i] = jobs[i][1]
24        i += 1
25
26    i = 1
27    while i <= n:
28        s, e, w = jobs[i - 1]
29
30        lo = 0
31        hi = i - 1
32        while lo < hi:
33            mid = (lo + hi) >> 1
34            if ends[mid] <= s:
35                lo = mid + 1
36            else:
37                hi = mid
38        p = lo
39        if p > 0 and ends[p - 1] > s:
40            p -= 1
41        while p < i - 1 and ends[p] <= s:
42            p += 1
43        if p == i - 1 and ends[p] <= s:
44            prev = i - 1
45        elif p >= 0 and ends[p] <= s:
46            prev = p + 1
47        else:
48            prev = 0
49
50        take = dp[prev] + w
51        skip = dp[i - 1]
52        dp[i] = take if take > skip else skip
53        i += 1
54
55    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