Skip to content
Tutorials Center
My learning

Topics

Lesson 162 of 225 ยท Dynamic Programming

Weighted Job Scheduling and Largest Divisible Subset

Solve weighted job scheduling with DP and binary search, then the largest divisible subset with a LIS-style chain DP. Python code with rebuilt answers.

Two classic dynamic programs share one idea: sort first, then let each item look back at the best compatible earlier item. In weighted job scheduling the "earlier compatible item" is a job that finishes before this one starts, and you find it with binary search. In largest divisible subset it is a smaller number that divides this one, and you find it by scanning. Both are cousins of the longest increasing subsequence.

You will also see why the greedy idea from interval scheduling breaks the moment jobs have different profits.

Weighted job scheduling

Problem. Each job has a start time, an end time and a profit. You have one machine, so you can only run jobs whose time ranges do not overlap (a job that starts exactly when another ends is fine). Choose a set of non-overlapping jobs with the maximum total profit.

If every profit were 1, the greedy rule "always take the job that ends first" would be optimal. With profits it fails. Take jobs (1, 10, profit 100), (1, 2, profit 1), (3, 4, profit 1): greedy by end time grabs the two tiny jobs for 2, while the long job is worth 100.

The DP

Sort jobs by end time. Let best[i] be the maximum profit using only the first i jobs (in that order). For job i there are two choices:

  • Skip it: the answer is best[i-1].
  • Take it: its profit plus the best answer among jobs that finish no later than job i starts. Let p(i) be the index of the last such job.
TEXT
best[i] = max( best[i-1], profit[i] + best[p(i)] )

Because the jobs are sorted by end time, the compatible jobs always form a prefix, so p(i) can be found with binary search on the list of end times. That gives O(n log n) overall, instead of O(n^2) with a linear scan.

Python Weighted job scheduling with rebuilt schedule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the call bisect_right(ends, start, 0, i - 1). It counts how many of the earlier jobs end at or before start. Using bisect_right (not bisect_left) is what lets a job start exactly when another ends. If your problem says boundaries must not touch, use bisect_left instead. See binary search for the difference between the two.

Checking against brute force

Whenever you write a DP with a clever lookup, test it against an exhaustive version on small random inputs. Trying all 2^n subsets is slow but obviously right.

Python Random test against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you ever see a mismatch, print the failing input: small failing cases are the fastest way to find an off-by-one in the binary search.

Complexity and variants

Sorting costs O(n log n), and each of the n binary searches costs O(log n). Memory is O(n). The same shape solves "maximum profit in job scheduling", "meeting rooms with value", and "choose non-overlapping events to attend for maximum total reward".

Largest divisible subset

Problem. Given distinct positive integers, find the largest subset in which every pair (a, b) satisfies a % b == 0 or b % a == 0. For [1, 2, 4, 8, 3, 9, 27] one answer is [1, 2, 4, 8]; another is [1, 3, 9, 27].

The key fact: if you sort the numbers, then in a valid subset each element only needs to divide the next one. Divisibility is transitive: if a | b and b | c, then a | c. So we only have to check the last element of the chain we extend.

Sort ascending, and let size[i] be the length of the longest divisible chain that ends at nums[i]:

TEXT
size[i] = 1 + max( size[j] for j < i if nums[i] % nums[j] == 0 )

That is exactly the O(n^2) LIS recurrence from the LIS lesson, with "greater than" replaced by "is a multiple of". Keep a parent array to rebuild the chain.

Python Largest divisible subset

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The time is O(n^2) and space O(n). Unlike LIS, there is no known O(n log n) patience-sorting trick, because "is a multiple of" is not a total order on the numbers. Two incomparable values such as 6 and 10 can both sit before 60, and a single tail table cannot track that.

Whenever a problem says "longest chain where each step must satisfy a relation", sort so the relation points forward, then use the LIS recurrence with that relation. The same recipe solves Russian-doll envelopes, longest string chain and box stacking.

Common mistakes

  • Forgetting to sort. Both algorithms rely on the order. Weighted jobs need end times ascending; the divisible chain needs numbers ascending.
  • bisect_left versus bisect_right. One treats touching jobs as overlapping, the other does not. Decide from the problem statement and test the boundary case.
  • Searching the whole array in the binary search. Restrict it to the earlier jobs (hi = i - 1) or a job with zero length could match itself.
  • Returning only the size. Interview versions often ask for the actual subset or schedule, so keep a parent or take array from the start.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the greedy rule 'pick the job that ends first' fail for weighted job scheduling?

    The rule optimizes the number of jobs, not their value. A long high-profit job can be worth more than any set of short ones it overlaps.
  2. 2. After sorting by end time, how is the last compatible earlier job found quickly?

    End times are sorted, so the jobs that finish no later than this start form a prefix, and bisect_right finds its length in O(log n).
  3. 3. What is the time complexity of weighted job scheduling with binary search?

    Sorting costs O(n log n), and n binary searches cost O(n log n) in total.
  4. 4. Why is it enough for each element of a sorted divisible chain to divide only the next element?

    If a divides b and b divides c, then a divides c, so checking adjacent pairs guarantees every pair is divisible.
  5. 5. Which classic recurrence does the largest divisible subset DP copy?

    size[i] = 1 + max(size[j]) over earlier j that satisfy a relation, here divisibility instead of 'smaller than'.

Summary

  • Weighted job scheduling: sort by end time, best[i] = max(best[i-1], profit[i] + best[p(i)]), find p(i) with bisect_right; O(n log n).
  • Greedy-by-end-time only works when all jobs are worth the same; with profits you need DP.
  • Largest divisible subset: sort, then LIS-style size[i] = 1 + max(size[j]) where nums[i] % nums[j] == 0; O(n^2), rebuild with parent.
  • "Sort, then look back at compatible items" is a reusable DP recipe; always test it against a brute force on small random inputs.

Next: Word Wrap, Box Stacking and Tile Stacking, more DPs that reuse the same chain idea.