您的当前位置：首页贪心算法经典例题：1，选择不相交区间 2，区间选点 3，区间覆盖

贪心算法经典例题：1，选择不相交区间 2，区间选点 3，区间覆盖

来源：爱够旅游网

1，选择不相交区间：数轴上有n个开区间（ai,bi）。选择尽量多个区间，是的这些区间两两没有公共点

#include <stdio.h>
#include <stdlib.h>
#include<algorithm>
using namespace std;
//选择不想交区间
struct Node{
int x, y;
}map[100+10];

int cmp(Node a, Node b){
if(a.y != b.y) return a.y < b.y;
return a.x < b.y;
}

int main(){
   int n;
   scanf("%d", &n);
   for(int i = 0; i < n; i++){
       scanf("%d %d" , &map[i].x, &map[i].y);
   }
   sort(map,map+n,cmp);
   //开始判断，第一个区间是一定要选的
   int start = map[0].y;
   int count = 1; //选了第一个,直接从第一个的后端点开始
   int n_last = n-1; //剩余区间数目

   while(n_last > 0){
       if(map[n-n_last].x >= start){
           count++;

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务