Independent task selection
Choose one of 200, 322, 56, or 207. Read the linked contract. Record whether you have seen the problem before, then submit code, reasoning, complexity, and boundary checks.
Job-selection problem
Input: 1..12 jobs [start,end,reward], with integer times 0..30, start<end, reward 0..20. Output: maximum reward obtainable without overlap. Touching endpoints are allowed; selecting no jobs is allowed. Example: [[0,2,3],[2,4,3],[0,4,10]] → 10. No input mutation is allowed.
Submit your function, an argument covering all possible selections, time/space costs, and a small independently checked input.
Work through a smaller schedule
Use jobs A=[0,2,4], B=[2,3,3], C=[1,4,8]. A and B can both run because A ends when B starts. Their reward is 7; C overlaps each and gives 8. Draw the occupied half-open intervals [start,end) before choosing an algorithm.
Sorting by end time creates prefixes. Define dp[i] as the best reward using the first i sorted jobs; dp[0]=0 permits the empty choice. For the current job, either skip it and retain the preceding best, or take its reward plus the best prefix whose jobs end by its start. These two cases cover every valid selection.
| Job | Earlier compatible prefix length | Skip | Take | New best |
|---|---|---|---|---|
| A: [0,2,4] | 0 | 0 | 4+0=4 | 4 |
| B: [2,3,3] | 1 | 4 | 3+4=7 | 7 |
| C: [1,4,8] | 0 | 7 | 8+0=8 | 8 |
Implement weighted_jobs(jobs) in student_week_08.py. Use sorted(jobs, key=…) to preserve the input. For each sorted job, scan earlier jobs to find the last compatible one and convert its zero-based index to a prefix length. Compute take before writing dp[i+1]. The answer is dp[n], not the reward of the last job.
python trace_lab.py --case weighted_jobs
python trace_lab.py --case weighted_jobs --student
python verify.py --student
The trace executes the reference implementation or your implementation on the table’s three jobs. Observe ordered, compatible, and dp. Sorting costs O(n log n); all predecessor scans total 0+1+…+(n−1), so this implementation takes O(n²) time. The sorted outer list and dp array occupy O(n) extra space; the returned number is O(1). No job record is changed.
For an independent check on n≤12, enumerate the subsets, sort each selected subset by time, reject overlapping neighbors, and compare the best reward. This slower checker uses O( n log n) time and O(n) working storage when subsets are processed one at a time. Test touching endpoints, identical intervals, zero rewards, and an example where the largest individual reward loses to two compatible jobs. Explain why selecting the earliest-finishing job alone is insufficient for weighted rewards.
Return to the original three-job assessment and write its own state table. For the selected LeetCode task, use the relevant Week 5, Week 6, or Week 7 input contract and trace, then create a different test input.