编辑代码

#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
using namespace std;
struct Section
{
	string name;
    double start;
    double end;
    Section(string n,int s, int e)
	{
		name=n;
        start = s;
        end = e;
    }
};
void printNonIntersectSections(list<Section> &nonIntersectSections) //输出选中的课程 
{
    for (list<Section>::iterator i = nonIntersectSections.begin(); i != nonIntersectSections.end(); ++i)
    {
        cout<<i->name<<" "<<i->start<<"~"<<i->end<<endl;
	}
    cout << endl;
}
void printNonIntersectSections(vector<Section> &sections) //输出全部的课程 
{
    for (vector<Section>::iterator i = sections.begin(); i != sections.end(); ++i)
    {
        cout<<i->name<<" "<<i->start<<"~"<<i->end<<endl;
	}
    cout << endl;
}
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) 
        {
            // 满足限制条件
            if (nonIntersectSections.size() > 0)
            {
                // 已经选出了区间，判断当前这个区间和选出区间是否相交
                // 不相交，且end值最小，记下的迭代器（位置），记下最小的end值
                if (nonIntersectSections.back().end <= i -> start && sectionEnd >= i -> end)
                {
                    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("高数",8.00, 9.30));
    sections.push_back(Section("电子商务",8.30, 10.00));
    sections.push_back(Section("数据结构", 9.30, 12.00));
    sections.push_back(Section("计算机基础", 10.00, 11.00));
    sections.push_back(Section("C语言", 11.30, 12.30));
    
    list<Section> nonIntersectSections;

    findNonIntersectSections(sections, nonIntersectSections);
    cout<<"全部课程如下："<<endl<<endl;
    printNonIntersectSections(sections);
	cout<<"选中的课程有："<<endl<<endl; 
    printNonIntersectSections(nonIntersectSections);
}