编辑代码

#include <iostream>
#include <algorithm>
#include <list>
#include <vector>

using namespace std;

struct Section {
        int start;
        int end;

        Section(int s, int e) {
            start = s;
            end = e;
        }
};


void printNonIntersectSections(list<Section> &nonIntersectSections) {
    for (list<Section>::iterator i = nonIntersectSections.begin(); i != nonIntersectSections.end(); ++i)
    {
        cout << "[" << i->start << "," << i->end << "] ";
    }

    cout << endl;
    
}

bool compareSectionLength(Section left, Section right) {
    return (left.end - left.start) < (right.end - right.start);
}

bool compareSectionStart(Section left, Section right) {
    return left.start < right.start;
}

void findNonIntersectSections(vector<Section> &sections, list<Section> &nonIntersectSections) {
    //按照从小到大顺序对区间起始点进行排序
    sort(sections.begin(), sections.end(), compareSectionStart);

    
    vector<Section>::iterator selected = sections.begin();

    while(selected != sections.end())
    {
        // 每次找出End最小的,且和已选出来的线段不相交的线段，因为它对期望值贡献最大，因为剩余的区间最大
        int sectionEnd = selected->end;//记录未选择过的线段起始的终止值
        vector<Section>::iterator minEndIterator = sections.end();//最小值的一个位置，等于end表示不指向任何值
        // 从起始到终止找出结束点最小的且不相交的线段
        for(vector<Section>::iterator i = selected; i != sections.end(); ++i) 
        {
            cout << "start: " << i -> start << " end: " << i -> end << endl;
            cout << sectionEnd << endl;
            cout << nonIntersectSections.size() << endl;

            // 满足限制条件
            if (nonIntersectSections.size() > 0)
            {
                // 已经选出了区间，判断当前这个区间和选出区间是否相交
                // 不相交，且end值最小，记下的迭代器（位置），记下最小的end值
                if (nonIntersectSections.back().end <= i -> start && sectionEnd >= i -> end)
                {
                    cout << "start: " << nonIntersectSections.back().start << " end: " << nonIntersectSections.back().end << endl;
                    minEndIterator = i;
                    sectionEnd = i -> end;
                }
            }
            else
            {
                // 没有选出区间
                if (sectionEnd >= i -> end)
                {
                    minEndIterator = i;
                    sectionEnd = i -> end;
                }
            }
            
        }

        // 如果minEndIterator不是结束的迭代器
        if ( minEndIterator != sections.end())
        {
            // 找到了最小的end，选出了区间
            selected = minEndIterator;
            nonIntersectSections.push_back(*selected);
           
        }
        // 从它的下一个区间继续找不相交的线段
         ++selected;
        

    }

    
}

int main(){
    vector<Section> sections;
    sections.push_back(Section(6, 8));
    sections.push_back(Section(2, 4));
    sections.push_back(Section(3, 5));
    sections.push_back(Section(1, 5));
    sections.push_back(Section(5, 9));
    sections.push_back(Section(8, 10));

    list<Section> nonIntersectSections;

    findNonIntersectSections(sections, nonIntersectSections);

    printNonIntersectSections(nonIntersectSections);
}