dw14_.cpp

区间覆盖问题的算法实现 问题描述：给出x轴上N条线段的坐标

#include<iostream.h>
const int N=6;
const int M=4;
struct segment_T
{int left;
int right;
int flag;
};
void input(segment_T data[],int number)
{for(int i=0;i<number;i++)
{cin>>data[i].left>>data[i].right;
data[i].flag=0;
}
}
void selection_sort(segment_T data[],int number)
{segment_T temp;int i,j;
for( i=0;i<number-1;i++)
for( j=i+1;j<number;j++)
if(data[i].left>data[j].left)
{temp=data[i];
data[i]=data[j];
data[j]=temp;
}
}
void output(segment_T data[],int number)
{
for(int i=0;i<number;i++)
	if(data[i].flag!=0)
	cout<<"["<<data[i].left<<","<<data[i].right<<"] ";
    }
void main()
{segment_T segment[N];int start=0,end=M,i=0,sum=0;
input(segment,N);
selection_sort(segment,N);
while(segment[i].right<=start)
	  i++;
while(segment[i].left>=end)
i++;
while(i<N&&segment[i].left<end)
{int max=0,k=-1;
while(segment[i].left<=start)
{if(max<(segment[i].right-start))
{k=i;
max=segment[i].right-start;
}
i++;
}
if(segment[i].left<=segment[i-1].right)
start=segment[i-1].right;
else i=N;
if(k!=-1)
{segment[k].flag=1;sum++;}
}

if (i==N) cout<<"无解."; 
else 
{cout<<"用"<<sum<<"条线段："<<endl;
output(segment,N);}
}