Algorithm Design Techniques: Greedy Approach for Interval Scheduling
Learn about greedy algorithms, with a focus on Interval Scheduling. Understand how to break down complex problems into smaller sub-problems, make optimal decisions, and prove correctness. Explore examples and the process of designing and analyzing greedy algorithms effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Basic Algorithm Design Techniques Divide and conquer Dynamic Programming Greedy Analyzing running time Design algorithm Proof of correctness Common Theme: To solve a large, complicated problem, break it into many smaller sub-problems.
Greedy Algorithm If a problem requires to make a sequence of decisions, for the first decision, make the best choice given the current situation. (This automatically reduces the problem to a smaller sub-problem which requires making one fewer decisions)
Warm-up: Walking in Manhattan Walk in a direction that reduces distance to the destination.
Greedy does not always work Driving in New York: one-way streets, traffic
Design and Analysis Designing a Greedy Algorithm: 1. Break the problem into a sequence of decisions. 2. Identify a rule for the best option. Analyzing a Greedy Algorithm: Important! Often fails if you cannot find a proof. Technique: Proof by contradiction. Assume there is a better solution, show that it is actually not better than what the algorithm did.
Example 1: Interval Scheduling There are n meeting requests, meeting i takes time (si, ti) Cannot schedule two meeting together if their intervals overlap. Goal: Schedule as many meetings as possible. Example: Meetings (1,3), (2, 4), (4, 5), (4, 6), (6, 8) Solution: 3 meetings ((1, 3), (4, 5), (6, 8))
Designing the Algorithm Think of the problem as making a sequence of decisions (similar to Dynamic Programming) - schedule one meeting at each iteration Think of all the options for the first decision, use a simple criteria to select the best Question: Which meeting should we schedule first? A. The one that started earliest B. The one that ends earliest C. The one that takes least amount of time
Algorithm Always try to schedule the meeting that ends earliest Schedule 1. Sort the meetings according to end time 2. For i = 1 to n 3. If meeting i does not conflict with previous meetings 4. Schedule meeting i Why is this algorithm correct? Intuition: We will never regret our first choice because it is better than all other choices. But how do we prove this formally?
Proof of correctness in pictures I have scheduled the most number of possible meetings!
I have scheduled the most number of possible meetings! No you are wrong! There is a way to schedule more meetings.
Can you show me how to do that? Here are the first two meetings I scheduled. Yes, those are fine. I made the same decisions.
and this is my third meeting i3. i3 j3 Wait, you can t do that. You need to schedule meeting j3
My meeting i3 ends before your meeting j3, so if you swap j3 to i3, you are still OK right? i3 j3 i3 I guess you are right. Fine I will do that.
But isnt this the same thing? You could have swapped to my 5th meeting. OK you got me on the 3rd meeting. But you made another mistake on the 5th meeting!
OK, OK, you can keep all of your meetings, but I could still schedule a meeting jk+1!
That doesnt make any sense. If there is such a meeting, I must consider it after ik, and I would have scheduled that meeting! OK, you win.
