---
title: 'Maximum Profit in Job Scheduling | Dynamic Programming Explained'
source: 'https://youtube.com/watch?v=oT51NIpw7iE'
video_id: 'oT51NIpw7iE'
date: 2026-08-04
duration_sec: 74
---

# Maximum Profit in Job Scheduling | Dynamic Programming Explained

> Source: [Maximum Profit in Job Scheduling | Dynamic Programming Explained](https://youtube.com/watch?v=oT51NIpw7iE)

## Summary

This video explains the concept of dynamic programming through the classic job scheduling problem, where the goal is to maximize profit by selecting non-overlapping jobs. It contrasts the exponential brute-force approach with the efficient DP method, illustrating how each decision reduces to either skipping a job or taking it and jumping to the next non-overlapping one.

### Key Points

- **Problem Definition** [00:02] — Given a list of jobs with start time, end time, and profit, the goal is to pick jobs to maximize profit without overlapping.
- **Brute Force is Exponential** [00:17] — Trying all combinations of jobs becomes exponential in complexity.
- **DP Decision Framework** [00:31] — For each job, only two choices: skip it (move to next job) or take it (earn profit and jump to next non-overlapping job).
- **DP Array Filling** [00:45] — Example: Job A earns 20, B overlaps so skip (still 20), C follows A (20+70=90), D follows B (20+100=120). Each job builds on future answers.
- **Dynamic Programming Essence** [01:00] — Instead of trying all combinations, choose the best option at each step, which is the core of dynamic programming.

### Conclusion

Dynamic programming optimizes job scheduling by making optimal local decisions that build on future results, avoiding exponential time complexity.

## Transcript

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
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
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
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
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
visualizations on Hello Interview, and follow us for more.