# 算法设计与分析笔记0x02 —— 贪心法(1)

## Interval Scheduling

• Goal: 找到尽可能多的相容工作
• Greed Algorithm
• 排序 nlogn
• 起始时间(break)
• 结束时间(由早到晚)
• 时间长度(break)
• 冲突数量(break)
• 当前工作与已选择工作无冲突的话，选择当前工作 n
• Greedy algorithm Consider jobs in increasing order of finish time. Take each job provided it’s compatible with the ones already taken.

• Implementation O(nlogn)
• 记录A中结束时间最晚的工作 j*
• 工作j的开始时间晚于j*的结束时间，则与A无冲突

### Proof

• 证明贪心法为最优算法：
• 假设贪心法不是最优的
• i_1,i_2,…i_k 表示贪心法算出的工作集合
• j_i,j_2,…j_k 表示最优工作解
• i_1=j_1,i_2=j_2,…i_r=j_r，前r个工作，两集和相同，使r尽可能大
• 即$j_{r+1}$工作开始结束时间晚于$i_{r+1}$，将$j_{r+1}$替换为$i_{r+1}$，j工作序列依然为最优解

## Interval Partitioning

• Lower Bound on Optimal Solution
• Goal: 找到最少的教室数量来安排所有的课程
• Lecture j starts at sj and finishes at fj.
• Greedy algorithm
• 排序 nlogn
• 按照开始时间排序
• 若当前课程可以安排在已有教室则加入，不能安排则开新教室

• Implementation O(nlogn)
• 记录每个教室的最晚结束时间
• 检查空闲时间最早的教室

### Proof

• 找出在任意时刻，最多有多少门课在同时进行
• Key observation Number of classrooms needed >= depth (when it’s equal, it reaches optimal solution)
• Let d = number of classrooms that the greedy algorithm allocates.
• Classroom d is opened because we needed to schedule a job, say j, that is incompatible with all d-1 other classrooms.
• Since we sorted by start time, all these incompatibilities are caused by lectures that start no later than $s_j$.
• Thus, we have d lectures overlapping at time $s_j + \epsilon$.

## Scheduling to Minimizing Lateness

• Goal: minimize maximum lateness
• Greedy algorithm
• 排序
• 持续时间(break)
• 截止时间
• 最晚开始(使得不迟交)时间 smallest slack(break)

### Inversions 反转

• Def: 有两个任务(i,j)，i的截止时间早于j的截止时间，但是j被安排在i前面
• In greedy schedule, no idle time, no inversions.
• After we swap inversion jobs, lateness won’t increase.

### Proof

Greedy schedule S is optimal.
Define S* to be an optimal schedule that has the fewest number of inversions, and let’s see what happens.

• Can assume S* has no idle time.
• If S* has no inversions, then S = S*.
• If S* has an inversion, let i-j be an adjacent inversion.
• swapping i and j does not increase the maximum lateness and strictly decreases the number of inversions
• this contradicts definition of S*

## Greedy Analysis Strategies

• Greedy algorithm stays ahead Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm’s.
• Structural Discover a simple “structural” bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound.
• Exchange argument Gradually transform any solution to the one found by the greedy algorithm without hurting its quality.

## Shortest Path – Dijkstra’s Algorithm

• Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u.
• Initialize S = { s }, d(s) = 0.
• Repeatedly choose unexplored node v which minimizes
$$\pi(v)=min_{e=(u,v):u\in S}d(u)+l_e$$
add v to S, and set $d(v) = \pi(v)$.

### Proof of Correctness

Invariant. For each node $u \in S$, d(u) is the length of the shortest s-u path.
Pf. (by induction on |S|)
Base case: |S| = 1 is trivial.
Inductive hypothesis: Assume true for |S| = k >= 1.

• Let v be next node added to S, and let u-v be the chosen edge.
• The shortest s-u path plus (u, v) is an s-v path of length $\pi(v)$.
• Consider any s-v path P. We’ll see that it’s no shorter than $\pi(v)$.
• Let x-y be the first edge in P that leaves S, and let P’ be the subpath to x.
• P is already too long as soon as it leaves S.
$$l(p)\geq l(p’) + l(x,y) \geq d(x) + l(x,y) \geq \pi(y) \geq \pi(v)$$

### Implementation

For each unexplored node, explicitly maintain $\pi(v)=min_{e=(u,v):u\in S}d(u)+l_e$.

• Next node to explore = node with minimum $\pi(v)$.
• When exploring v, for each incident edge e = (v,w), update
$$\pi(w)=min(\pi(w),\pi(v)+l_e)$$
Efficient implementation. Maintain a priority queue of unexplored nodes, prioritized by $\pi(v)$.