[00:02] it's actually just one decision. You're given a list of jobs. Each job has a start time, an end time, and a profit. Your goal is to pick jobs to maximize profit, but they can't overlap. Most people will try all combinations, but
[00:17] that becomes exponential. A better option is to think like this. For every job, you only have two choices. Either skip it or take it. If you skip it, you just move to the next job. But if you take it, you earn its profit, and you
[00:31] jump to the next job that doesn't overlap, like taking job A and jumping straight to C. So, every decision becomes either skip it or take it and add the best profit from the next valid job. Now, watch the DP array fill. We
[00:45] job. Now, watch the DP array fill. We start with zero. Job A earns 20. Job B overlaps, so we skip. Still 20. Job C can follow A, so 20 + 70 is 90. Job D can follow A, so 20 + 70 is 90. Job D can follow B, so 20 + 100 is 120. Each
[01:00] job builds on future answers. You're not trying all combinations. You're choosing the best option at each step, and that's dynamic programming. Learn more problems like this with interactive visualizations on Hello Interview, and
[01:13] visualizations on Hello Interview, and follow us for more.