(贪心 线段不相交问题)codeVs 1214 线段覆盖

题目描述  Description

    给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

输入描述  Input Description

    输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出描述  Output Description

    输出第一行是一个整数表示最多剩下的线段数。

样例输入  Sample Input

3

6  3

1  3

2  5

样例输出  Sample Output

2

数据范围及提示  Data Size & Hint

0<N<100

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

贪心，注意输入的端点的两个数中，有可能并不是左边比右边小，要对他们进行转换。

C++代码：

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct segement{ int l,r; }se[103]; bool cmp(segement a,segement b){ if(a.r == b.r){ return a.l < b.l; } return a.r < b.r; } int main(){ int n; cin>>n; for(int i = 0; i < n; i++){ cin>>se[i].l>>se[i].r; if(se[i].l > se[i].r){ swap(se[i].l,se[i].r); } } sort(se,se+n,cmp); int sum = 1; int ans = se[0].r; for(int i = 1; i < n; i++){ if(ans <= se[i].l){ sum++; ans = se[i].r; } } cout<<sum<<endl; return 0; }

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10631821.html

相关资源：JAVA上百实例源码以及开源项目