#include <iostream>
#include <vector>

using namespace std;

int _count[100][100]; //构造最优矩阵
int p[100][100];
int numbers[100];
void dp(int start[], int finish[],int TASK_COUNT) {
    for (int len = 2; len <= TASK_COUNT + 2; len++) {
        for (int begin = 0; begin <= TASK_COUNT + 1; begin++) {
            int end = begin + len - 1;
            int max = 0;
            int slice = 0;
            int k;
            for (k = begin + 1; k <= end - 1; k++) {
                if (start[k] >= finish[begin]&&finish[k]<=start[end]) {
                    int temp = _count[begin][k] + _count[k][end] + 1;
                    if (temp > max) {
                        max = temp;
                        slice = k;
                    }
                }
            }
            p[begin][end] = slice;
            _count[begin][end] = max;
        }
    }
}
void printDp( int begin, int end) {
    int pos = p[begin][end];
    if (pos == 0)
        return;
    cout << numbers[pos] << " ";
    printDp(begin, pos);
    printDp(pos, end);
}
int main() {
    vector<int> vfinish;
    vector<int> vstart;
    //插入数组前置数值-1
    vstart.push_back(-1);
    vfinish.push_back(-1);
    int number;
    cout << "请分别输入各个事件的开始跟结束时间：" << endl;
    while (1){
        cin >> number;
        vstart.push_back(number);
        cin >> number;
        vfinish.push_back(number);
        if (cin.get() == '\n')
            break;
    }
    //插入数组后置数值255
    vstart.push_back(255);
    vfinish.push_back(255);
    int *start = new int[vstart.size()];
    if (!vstart.empty())
        memcpy(start, &vstart[0], vstart.size()*sizeof(int));
    int *finish = new int[vfinish.size()];
    if (!vfinish.empty())
        memcpy(finish, &vfinish[0], vfinish.size()*sizeof(int));
    int TASK_COUNT = vstart.size()-2;
    for(int i=0;i<vstart.size();i++)
        numbers[i]=i;
    cout << "图例如下：" << endl; //输出图示
    for (int i = 0; i <= TASK_COUNT; i++) {
        cout << i << ":";
        for (int j = 0; j < start[i]; j++) {
            cout << "  ";
        }
        for (int j = start[i]; j < finish[i]; j++)
            cout << "■";
        cout << endl;
    }
    for(int i=0;i<TASK_COUNT+2;i++){//按照结束时间排序
        for(int j=0;j<TASK_COUNT+1;j++){
            if(finish[j]>finish[j+1]){
                std::swap(finish[j],finish[j+1]);
                std::swap(start[j],start[j+1]);
                std::swap(numbers[j],numbers[j+1]);
            }
        }
    }
    for (int i = 0; i <= TASK_COUNT + 2; i++) {
        for (int j = 0; j <= TASK_COUNT + 2; j++) {
            _count[i][j] = 0;
            p[i][j] = 0;
        }
    }
    dp(start, finish, TASK_COUNT);
    cout << "总共可完成的事件个数为：" << _count[0][TASK_COUNT + 1] << endl;
    cout << "完成的事件为：";
    printDp(0, TASK_COUNT + 1);
    return 0;
}