编辑代码

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

struct Section {
        string name;
        float start;
        float end;

        Section(string a,float s, float e) {
            name =a;
            start = s;
            end = e;
        }
};


void printNonIntersectSections(list<Section> &nonIntersectSections) {
    for (list<Section>::iterator i = nonIntersectSections.begin(); i != nonIntersectSections.end(); ++i)
    {
        cout<<i->name;
        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 minEnd = sections.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)
            {
                
                if (nonIntersectSections.back().end <= i -> start && sectionEnd >= i -> end)
                {
                    cout << "start: " << nonIntersectSections.back().start << " end: " << nonIntersectSections.back().end << endl;
                    minEnd = i;
                    sectionEnd = i -> end;
                }
            }
            else
            {
                if (sectionEnd >= i -> end)
                {
                    minEnd = i;
                    sectionEnd = i -> end;
                }
            }
            
        }

        if ( minEnd != sections.end())
        {
            selected = minEnd;
            nonIntersectSections.push_back(*selected);
           
        }
        // 从它的下一个线段继续找不相交的线段
         ++selected;
        

    }

    
}

int main(){
    vector<Section> sections;
    sections.push_back(Section("高数",800, 930));
    sections.push_back(Section("电子商务",830, 1000));
    sections.push_back(Section("数据结构",930, 1200));
    sections.push_back(Section("计算机基础",1000, 1100));
    sections.push_back(Section("C语言",1130, 1230));


    list<Section> nonIntersectSections;

    findNonIntersectSections(sections, nonIntersectSections);

    printNonIntersectSections(nonIntersectSections);
}