Greedy Algorithm -Simple -Quick -Easy to program
-Greedy algorithms make the best choice at each decision without looking ahead. Greedy Algorithms for Time-Slot interval Optimization
#1)Pick the shortest intervals -pick the shortest -cross off all overlaps -pick the next shortest #2)Pick the intervals with lowest overlaps -pick the least overlaps -Cross off overlaps -Pick the next least overlap #3)Pick the earllest intervals #4)Pick the interval that finish the earllest #5)Start the latest Tree=connected algolic graph Spanning tree of graph Greedy =subset of edges of Greedy that form a tree & hit all vertices of G MST: given graph G:(v,E) & edge weights w:E=>R find a spanning tree T of minimum weight
- Optimal substucture: optimal solutions to problem incorporates optimal solutions to subproblem(s)
- greedy-choice property: locally optimal choics lead to globally optimal solution