线段覆盖问题

1. 最大不相交线段覆盖问题

问题描述：给定一组线段，选择尽可能多的线段，使得这些线段互不相交（即没有重叠部分）。

可以按照线段的右端点进行排序
然后依次选择右端点最小且不与已选线段相交的线段

CPP

#include<bits/stdc++.h>
using namespace std;

struct num{int l, r;};
bool cmp(num &a, num &b){
  return a.r < b.r; // 因为每次都要选择占用时间少的线段，所以按右端点进行排序
}

signed main(){
  int n;
  cin >> n;
  vector<num> a(n);
  for(int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;

  sort(a.begin(), a.end(), cmp);

  int R = INT_MIN, ans = 0;
  for(int i = 0; i < n; i++){
    if(a[i].l >= R){ // 寻找第一个左端点（脱离）大于该线段的其他线段
      ans ++;
      R = a[i].r;
    }
  }

  cout << ans << "\n";

  return 0;
}


// kasty's code

时间复杂度：

因为排序占时间多，所以总时间复杂度为:O(nlogn)

2. 最小线段覆盖区间问题

问题描述：给定一个目标区间和一组线段，选择最少数量的线段，使得它们的并集能够完全覆盖目标区间。

按照线段的左端点排序
在每一步选择能够覆盖当前起点且右端点最大的线段

CPP

#include<bits/stdc++.h>
using namespace std;

struct num{int l, r;};
bool cmp(num &a, num &b){
  return a.l < b.l; // 为了占据更多的线段，所以依线段左端点进行排序
}

signed main(){
  int n, s, e;
  cin >> n >> s >> e;
  vector<num> a(n);
  for(int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;

  sort(a.begin(), a.end(), cmp);

  int R = s, ans = 0, i = 0;
  for(int k = 0; k < n && R < e; k++){
    int med = R;
    while(i < n && a[i].l <= R) med = max(med, a[i].r), i ++;
    if(med == R) {cout << "-1\n"; return 0;} // 没有找到下一个线段，退出  
    ans ++;
    R = med;
  }

  if(R >= e) cout << ans << "\n";
  else cout << "-1\n"; // 没有线段可以拼接

  return 0;
}


// kasty's code

时间复杂度：

时间复杂度仍然是:O(n log n)（排序）+ O(n)（扫描）

3.最小点覆盖所有线段问题

问题描述：给定一组线段，计算需要多少个点可以占据所有线段（线段可以重合）

按右端点排序：将所有区间按照右端点升序排序
贪心选点：初始化一个空点集 points，然后遍历排序后的区间：
1. 如果当前区间不包含任何已选的点，则选择它的右端点作为新点，并加入 points。
2. 否则，跳过（因为它已经被某个点覆盖）。

CPP

#include<bits/stdc++.h>
using namespace std;

struct num{int l, r;};
bool cmp(num &a, num &b){
  return a.r < b.r; // 我们希望有更多线段重合，所以按右端点排序
}

signed main(){
  int n;
  cin >> n;
  vector<num> a(n);
  for(int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;
  
  sort(a.begin(), a.end(), cmp);

  int ans = 0, R = -1;
  for(int i = 0; i < n; i++){
    if(a[i].l > R){ // 如果该线段的左端点大于前继线段的右端点，说明没有和前线段重合
      R = a[i].r;
      ans ++;
    }
  }

  cout << ans << "\n";

  return 0;
}


// kasty's code

时间复杂度：

时间复杂度仍然是:O(n log n)

线段覆盖问题

文章操作

线段覆盖问题

1. 最大不相交线段覆盖问题

2. 最小线段覆盖区间问题

3.最小点覆盖所有线段问题

相关推荐

评论

线段覆盖问题