Solution #c90b917a-c0e6-41a7-9b36-81bb36459e9d

completed

Score

80% (4/5)

Runtime

15μs

Delta

-20.0% vs best

First in chain

Code

def solve(input):
    jobs = input["jobs"]
    # Sort jobs based on their end time
    jobs.sort(key=lambda job: job[1])

    # Function to perform binary search to find the last non-conflicting job
    def find_last_non_conflicting(jobs, index):
        low, high = 0, index - 1
        while low <= high:
            mid = (low + high) // 2
            if jobs[mid][1] <= jobs[index][0]:
                if jobs[mid + 1][1] <= jobs[index][0]:
                    low = mid + 1
                else:
                    return mid
            else:
                high = mid - 1
        return -1

    # Dynamic programming table to store the maximum weight up to each job
    n = len(jobs)
    dp = [0] * n
    dp[0] = jobs[0][2]

    for i in range(1, n):
        # Include the current job
        include_weight = jobs[i][2]
        last_non_conflicting = find_last_non_conflicting(jobs, i)
        if last_non_conflicting != -1:
            include_weight += dp[last_non_conflicting]

        # Exclude the current job
        exclude_weight = dp[i - 1]

        # Take the maximum of including or excluding the current job
        dp[i] = max(include_weight, exclude_weight)

    # The last entry in dp table will have the result
    return dp[-1]

Compare with Champion

Score Difference

-20.0%

Runtime Advantage

3μs faster

Code Size

39 vs 39 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 jobs = input["jobs"]2 if not isinstance(input, dict):
3 # Sort jobs based on their end time3 return 0
4 jobs.sort(key=lambda job: job[1])4 raw = input.get("jobs")
55 if not raw:
6 # Function to perform binary search to find the last non-conflicting job6 return 0
7 def find_last_non_conflicting(jobs, index):7
8 low, high = 0, index - 18 jobs = []
9 while low <= high:9 for j in raw:
10 mid = (low + high) // 210 if isinstance(j, (list, tuple)) and len(j) == 3:
11 if jobs[mid][1] <= jobs[index][0]:11 jobs.append((j[1], j[0], j[2])) # sort by end, store as (end, start, weight)
12 if jobs[mid + 1][1] <= jobs[index][0]:12 if not jobs:
13 low = mid + 113 return 0
14 else:14
15 return mid15 jobs.sort()
16 else:16 ends = []
17 high = mid - 117 bests = []
18 return -118
1919 for e, s, w in jobs:
20 # Dynamic programming table to store the maximum weight up to each job20 lo = 0
21 n = len(jobs)21 hi = len(ends)
22 dp = [0] * n22 while lo < hi:
23 dp[0] = jobs[0][2]23 mid = (lo + hi) >> 1
2424 if ends[mid] <= s:
25 for i in range(1, n):25 lo = mid + 1
26 # Include the current job26 else:
27 include_weight = jobs[i][2]27 hi = mid
28 last_non_conflicting = find_last_non_conflicting(jobs, i)28
29 if last_non_conflicting != -1:29 candidate = w + (bests[lo - 1] if lo else 0)
30 include_weight += dp[last_non_conflicting]30 current = bests[-1] if bests else 0
3131
32 # Exclude the current job32 if candidate > current:
33 exclude_weight = dp[i - 1]33 if ends and ends[-1] == e:
3434 bests[-1] = candidate
35 # Take the maximum of including or excluding the current job35 else:
36 dp[i] = max(include_weight, exclude_weight)36 ends.append(e)
3737 bests.append(candidate)
38 # The last entry in dp table will have the result38
39 return dp[-1]39 return bests[-1] if bests else 0
Your Solution
80% (4/5)15μs
1def solve(input):
2    jobs = input["jobs"]
3    # Sort jobs based on their end time
4    jobs.sort(key=lambda job: job[1])
5
6    # Function to perform binary search to find the last non-conflicting job
7    def find_last_non_conflicting(jobs, index):
8        low, high = 0, index - 1
9        while low <= high:
10            mid = (low + high) // 2
11            if jobs[mid][1] <= jobs[index][0]:
12                if jobs[mid + 1][1] <= jobs[index][0]:
13                    low = mid + 1
14                else:
15                    return mid
16            else:
17                high = mid - 1
18        return -1
19
20    # Dynamic programming table to store the maximum weight up to each job
21    n = len(jobs)
22    dp = [0] * n
23    dp[0] = jobs[0][2]
24
25    for i in range(1, n):
26        # Include the current job
27        include_weight = jobs[i][2]
28        last_non_conflicting = find_last_non_conflicting(jobs, i)
29        if last_non_conflicting != -1:
30            include_weight += dp[last_non_conflicting]
31
32        # Exclude the current job
33        exclude_weight = dp[i - 1]
34
35        # Take the maximum of including or excluding the current job
36        dp[i] = max(include_weight, exclude_weight)
37
38    # The last entry in dp table will have the result
39    return dp[-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