线段覆盖/n/n## 题目描述/n/n给定 $x$ 轴上的 $N$（$0<N<100$）条线段，每个线段由它的二个端点 $a_i$ 和 $b_i$ 确定，$i=1,2,/dots,N$，这些坐标都是区间 $(－999,999)$ 的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。/n/n## 输入格式/n/n从标准输入读入数据。/n输入第一行是一个整数 $N$。接下来有 $N$ 行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。/n/n## 输出格式/n/n输出到标准输出。/n输出第一行是一个整数表示最多剩下的线段数。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n3/n6 3/n1 3/n2 5/n/n/n### 样例输出 #1/n/n/n2/n/n/n## 代码实现/n/ncpp/n#include <iostream>/n#include <vector>/n#include <algorithm>/n/nusing namespace std;/n/n// 自定义线段结构体/nstruct Segment {/n int start;/n int end;/n/n Segment(int s, int e) : start(s), end(e) {}/n};/n/n// 比较函数，按照线段的起点从小到大排序/nbool compare(Segment s1, Segment s2) {/n return s1.start < s2.start;/n}/n/nint main() {/n int n;/n cin >> n;/n/n vector<Segment> segments;/n/n // 读取线段数据/n for (int i = 0; i < n; i++) {/n int start, end;/n cin >> start >> end;/n segments.push_back(Segment(start, end));/n }/n/n // 按照起点排序/n sort(segments.begin(), segments.end(), compare);/n/n int count = 0; // 剩余线段的数量/n/n int end = segments[0].end; // 当前线段的结束点/n for (int i = 1; i < n; i++) {/n // 如果当前线段的起点大于前一个线段的结束点，则说明两条线段没有内部公共点/n // 可以保留这条线段/n if (segments[i].start > end) {/n count++;/n end = segments[i].end;/n }/n // 如果当前线段的起点小于等于前一个线段的结束点，则说明两条线段有内部公共点/n // 需要保留前一个线段的结束点更大的那条线段，舍弃当前线段/n else {/n if (segments[i].end > end) {/n end = segments[i].end;/n }/n }/n }/n/n cout << count << endl;/n/n return 0;/n}/n