区间选点有关问题，求源代码

区间选点问题，求源代码。
区间选点问题

　　【例2】数轴上有n个闭区间[ai,bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

------解决方案--------------------
lz画个图就可以了

C/C++ code

#include <iostream>
using namespace std;


struct  Period 
{
    float begin;
    float end;
};

void Swap(Period &per1,Period &per2)
{
    Period temp;
    temp=per1;
    per1=per2;
    per2=temp;
}


void Sort(Period *peiodGroup,int len)//pop sort by peiodGroup[i].begin
{
    int i,j;
    for (j=len-1;j>0;j--)
    {
        for (i=0;i<j;i++)
        {
            if (peiodGroup[i].begin>peiodGroup[i+1].begin)
            {
                Swap(peiodGroup[i],peiodGroup[i+1]);
            }
        }
    }
}

int  Count(Period *peiodGroup,int len)//notice:the peiodGroup has been sorted
{
    int dotCount=1;
    int i;
    float curEnd=peiodGroup[0].end;

    for (i=1;i<len;i++)
    {
        if (peiodGroup[i].begin<=curEnd)
        {
            ;
        }
        else
        {
            dotCount++;
            curEnd=peiodGroup[i].end;
        }
    }

    return dotCount;
}

int main()
{
    int len;
    cin>>len;//区间 个数
    Period *peiodGroup=new Period[len];
    //input
    int i;
    for (i=0;i<len;i++)
    {
        cin>>peiodGroup[i].begin>>peiodGroup[i].end;
    }

    Sort(peiodGroup,len);
    //output the sorted  peiodGroup
    for (i=0;i<len;i++)
    {
        cout<<peiodGroup[i].begin<<","<<peiodGroup[i].end<<endl;
    }
    //
    int dotCount=Count(peiodGroup,len);
    cout<<dotCount<<endl;
}

区间选点有关问题，求源代码

相关推荐