数轴上有 n 条线段,第 i (1≤i≤n) 条线段覆盖的范围是 ai 到 bi,请问最多可以从中选出几条线段,使得任意两条选出的线段都没有重叠部分(有一个公共点也算重叠,比如说一条线段从 1 覆盖到 2,另一条线段从 2 覆盖到 3,这两条线段也算有重叠部分)? 给出c++的代码
时间: 2023-02-23 20:16:52 浏览: 202
这个问题可以用贪心算法来解决。
首先将线段按照右端点从小到大排序,然后依次考虑每条线段。如果当前线段的左端点大于前面选出线段的右端点,那么就可以选择当前线段。
代码如下:
```
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
struct Seg {
int l,r;
bool operator < (const Seg &x) const {
return r<x.r;
}
} a[N];
int n;
int main() {
cin>>n;
for(int i=0;i<n;i++) {
cin>>a[i].l>>a[i].r;
}
sort(a,a+n);
int ans=0,lastr=-1;
for(int i=0;i<n;i++) {
if(a[i].l>lastr) {
ans++;
lastr=a[i].r;
}
}
cout<<ans<<endl;
return 0;
}
```
该代码实现了贪心算法,用于解决上面给出的问题。
相关问题
数轴上有 n 条线段,第 i (1≤i≤n) 条线段覆盖的范围是 ai 到 bi,请问最多可以从中选出几条线段,使得任意两条选出的线段都没有重叠部分(有一个公共点也算重叠,比如说一条线段从 1 覆盖到 2,另一条线段从 2 覆盖到 3,这两条线段也算有重叠部分)?
这是一道线段覆盖问题,一般可以通过贪心算法来解决。具体方法如下:
1. 将所有线段按照右端点升序排列。
2. 遍历每一条线段,如果当前线段的左端点大于前一条线段的右端点,则选择当前线段。
3. 统计选择的线段数即为答案。
因为每一次都选择的是右端点最小的线段,因此保证了不存在重叠部分。
在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分,问最大的k为多少?
这个问题可以使用贪心算法来解决。具体地,我们可以按照线段的右端点从小到大排序,然后依次选择右端点最小的未被选择的线段,直到选出k条线段为止。这是因为右端点越靠左的线段,留给其他线段的空间就越小,因此先选右端点小的线段可以留出更多的空间给其他线段。
这个算法的时间复杂度为O(nlogn),其中n为线段的数量。