wikioi 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

6 3

1 3

2 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

0<N<100

思路：求没有公共节点的最多的线段数，这个问题跟活动安排是一样的，用贪心算法，把线段右节点按递增排列，每次总是选择右节点最小的线段加入当前的最优线段集合，使该集合能够最大限度地容纳更多的线段。

/*

作者:t_rex

题目:p1214 线段覆盖

*/

#include <iostream>

using namespace std;

int k[100][2];

void quicksort(int a[][2], int b, int e){

 //快速排序

  if(b >= e)

    return;

  int i = b, j = e + 1, n, m;

  int x = a[i][1], y = a[i][0];

  while(true){

    while(a[++i][1] < x && i < j);

    while(a[--j][1] > x);

    if(i >= j)

        break;

    else{

        n  = a[i][0], m = a[i][1];

        a[i][0] = a[j][0], a[i][1] = a[j][1];

        a[j][0] = n, a[j][1] = m;

    }

  }

  a[b][0] = a[j][0], a[b][1] = a[j][1];

  a[j][0] = y, a[j][1] = x;

  quicksort(a, j+1, e);

  quicksort(a, b, j-1);

}

int main(){

  int n, i = 0, a, b, cnt = 1, prev = 0;

  cin >> n;

  for(; i < n; i++){

      cin >> a >> b;

      if(a < b) swap(a, b);

      k[i][0] = b, k[i][1] = a;

  }

  quicksort(k, 0, n-1);

  for(i = 1; i < n; i++)

      if(k[prev][1] <= k[i][0]) cnt++, prev = i;

  cout << cnt ;

  return 0;

}

秒客网

wikioi 1214 线段覆盖

相关文章