第四章-贪心算法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct node
{
    int start, end;
}node;

int n;
vector<node> v;

bool Compare(node n1, node n2)
{
    return n1.end < n2.end;
}

void Setup()
{
    cin >> n;
    node t;
    for (int i = 0; i < n; i++)
    {
        cin >> t.start >> t.end;
        v.push_back(t);
    }
    sort(v.begin(), v.end(), Compare);
}

int Select()
{
    int maxCount = 1;
    int currectAct = 0;
    for (int i = 1; i < n - 1; i++)        //直接从第二个开始
    {
        if (v[i].start >= v[currectAct].end)
        {
            maxCount++;
            currectAct = i;        //在当前基础上，继续找下一个
        }
    }
    return maxCount;
}

int main()
{
    Setup();
    cout << Select() << endl;
    return 0;
}