Greedy

Follow Algorithm Design 教科書的內容

4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead

• 435 - Non-overlapping Intervals

• 253 - Meeting Rooms II

4.2 Scheduling to Minimize Lateness:An Exchange Argument

• 630 - Course Schedule III

Exercise 4.5

Question: Let’s consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let’s suppose that despite the bucolic setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations.

Give an efficient algorithm that achieves this goal, using as few base stations as possible.

Ans: When there is a house not covered by any base station, we build one 4 miles after the house

Proof: Use math induction to show that the stations of our solution is always right to the optimal solution

• 452 - Minimum Number of Arrows to Burst Balloons

小小 Summary：

A Concise Template for "Overlapping Interval Problem"

寫 150 以內的題目

• 122 - Best Time to Buy and Sell Stock II

• 134 - Gas Station

• 135 - Candy