Week3：区间选点——局部贪心
区间选点
题目内容
数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）
输入格式
第一行1个整数N（N<=100）
第2~N+1行，每行两个整数a,b（a,b<=100）
输出格式
一个整数，代表选点的数目
样例
Input
2
1 5
4 6
Output
1
Input
3
1 3
2 5
4 6
Output
2
解题思路
本题采取局部贪心的策略。
对于输入完成之后的各个区间，对其进行排序：
- 区间尾越小的排在越前面
- 区间尾相同的时候，区间头越大的排在越前面
接下来的部分用一个例子来解释(图中已经按照上述规则排序好了)：
- 我们先选择区间一的end点，此时总点数count=1。不难发现，当第一个点选在这的时候，所有与其end点相同的区间都一定会有点了(因为我们已经排序过了)，把这里设置成curlast点。
- 接下来看之后的区间，在这时，如果遇到的区间的start点在我们当前的curlast之前，那么这个区间就可以跳过不管，因为已经有一个点在它的范围内了。(图中为区间2和区间3，这时候我们的curlast点依旧在红色处)
- 继续往下看，我们发现当我们遇到区间6的时候，其start点就在curlast之后了，也就是说，curlast点已经不能满足“区间6里有一个点了”，因此我们需要选第二个点，我们依旧选择end点。此时count=2，curlast在蓝色位置。
- 继续往下看，区间7的start点在curlast点之前，跳过。
- 区间8的start点在curlast点之后，所以我们同前两次的操作，更新curlast。现在count=3，curlast在绿色处。
- 我们发现已经遍历完了所有的区间，代码结束，结果为3；
代码
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct TimeCell
{int start;int end;TimeCell(int s,int e){start = s;end = e;}
};vector<TimeCell>timecell;bool cmp(const TimeCell& a, const TimeCell& b)
{if (a.end != b.end) return a.end < b.end;else return a.start > b.start;
}int main()
{int n, counter = 0;cin >> n;int tema, temb;for (int i = 0; i < n; i++){cin >> tema >> temb;timecell.push_back(TimeCell(tema, temb));}sort(timecell.begin(), timecell.end(), cmp);int curlast = timecell[0].end;counter++;for (int i = 1; i < timecell.size(); i++){if (curlast < timecell[i].start){curlast = timecell[i].end;counter++;}}cout << counter << endl;return 0;
}
Week3：区间选点——局部贪心
区间选点
题目内容
数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）
输入格式
第一行1个整数N（N<=100）
第2~N+1行，每行两个整数a,b（a,b<=100）
输出格式
一个整数，代表选点的数目
样例
Input
2
1 5
4 6
Output
1
Input
3
1 3
2 5
4 6
Output
2
解题思路
本题采取局部贪心的策略。
对于输入完成之后的各个区间，对其进行排序：
- 区间尾越小的排在越前面
- 区间尾相同的时候，区间头越大的排在越前面
接下来的部分用一个例子来解释(图中已经按照上述规则排序好了)：
- 我们先选择区间一的end点，此时总点数count=1。不难发现，当第一个点选在这的时候，所有与其end点相同的区间都一定会有点了(因为我们已经排序过了)，把这里设置成curlast点。
- 接下来看之后的区间，在这时，如果遇到的区间的start点在我们当前的curlast之前，那么这个区间就可以跳过不管，因为已经有一个点在它的范围内了。(图中为区间2和区间3，这时候我们的curlast点依旧在红色处)
- 继续往下看，我们发现当我们遇到区间6的时候，其start点就在curlast之后了，也就是说，curlast点已经不能满足“区间6里有一个点了”，因此我们需要选第二个点，我们依旧选择end点。此时count=2，curlast在蓝色位置。
- 继续往下看，区间7的start点在curlast点之前，跳过。
- 区间8的start点在curlast点之后，所以我们同前两次的操作，更新curlast。现在count=3，curlast在绿色处。
- 我们发现已经遍历完了所有的区间，代码结束，结果为3；
代码
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct TimeCell
{int start;int end;TimeCell(int s,int e){start = s;end = e;}
};vector<TimeCell>timecell;bool cmp(const TimeCell& a, const TimeCell& b)
{if (a.end != b.end) return a.end < b.end;else return a.start > b.start;
}int main()
{int n, counter = 0;cin >> n;int tema, temb;for (int i = 0; i < n; i++){cin >> tema >> temb;timecell.push_back(TimeCell(tema, temb));}sort(timecell.begin(), timecell.end(), cmp);int curlast = timecell[0].end;counter++;for (int i = 1; i < timecell.size(); i++){if (curlast < timecell[i].start){curlast = timecell[i].end;counter++;}}cout << counter << endl;return 0;
}
发布评论