有 n 项工作，每项工作分别在 Si 时间开始，在 Ti 时间结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（即使是开始的瞬间和结束的瞬间的重叠也是不允许的）。
你的目标是参与尽可能多的工作，那么最多能参与多少项工作呢？
a. 你能想到的解题思路或者解题方法是什么？请描述（2分）
b.请使用伪代码实现你的解题思路（4分）
c.请简单证明你所使用的方法是最优解（4分）
解答：
写出解题思路：
1）在可选的工作中，每次都选取用时最短的工作。 1分
2）在可选的工作中，每次都选取与最少可选工作有重叠的工作。1分
3）在可选的工作中，每次都选取结束时间最早的工作。2分（本题最优贪心策略）
4）使用穷举方式。1分
写出伪代码：
1）这个问题可以使用贪心算法进行求解，在可选的工作中，每次都选取结束时间最早的工作。（4分）
nconst int MAX_N = 100000;
int N, S[MAX_N], T[MAX_N];
pair<int, int> itv[MAX_N];
void solve() {
for (int i = 0; i < N; i++) {
itv[i].first = T[i];
itv[i].second = S[i];
}
sort(itv, itv + N);
int ans = 0, t = 0;
for (int i = 0; i < N; i++) {
if (t < itv[i].second) {
ans++;
t = itv[i].first;
}
}
printf("%d\n", ans);
}
2）使用穷举方式写伪代码。（2分）
算法证明过程：
1）使用归纳法，基本思想是证明这个条件在算法中的每一步都成立，即在 k 时成立， k + 1 时也成立；（4分）
2）使用反正法，基本思想是用贪心的策略，依次构造出一个解S1。假设最优解S2不同于S1，可以证明是矛盾的。（4分）
能基本表示其中证明思想即可
其他证明方式给分视情况而定。