# Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem.

I understand how the solution is implemented but, I'd love to see a proof of correctness for this solution (i.e. partial correctness and termination). If anyone can help me understand why this solution is correct mathematically in a general form, that'd really great!

• Have you ever read the proof for Kruskal's algorithm? A proposition similar to the proposition $P$ there can be proved by induction for this problem. If you can write an answer, I can check and upvote. – John L. May 20 at 4:13
• What is the weighted job scheduling problem? What is the greedy algorithm used to solve it? – Yuval Filmus May 20 at 5:49
• Hi @JohnL. I have read the proof you linked, but do not see how it's related. Can you link me to a proof of a solution (dynamic or greedy) to the Weighted Job Scheduling problem, please? :) – Kapernski May 20 at 6:52
• Try proving the following proposition by induction: If $A$ is the arrangement of the jobs at each stage of your algorithm right after a job is selected, there is an optimal arrangement of the jobs that extends $A$. – John L. May 21 at 23:09