C++ 排序电视节目：持续时间优先，开始时间次之

题目描述

寒假你决定收看若干电视节目，电视节目开始和结束时间表示为 [ai,bi]，其中 ai, bi 为整数，由于你每看一个电视节目收获值相同，因此决定优先收看持续时间更短的节目，如果持续时间都相同，那么你优先收看开始时间早的，否则收看编号靠前的。请你按输入顺序给节目编号，输出排序后的编号。

代码实现

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

// 定义电视节目结构体
struct Program {
    int start;  // 开始时间
    int end;    // 结束时间
    int index;  // 编号

    // 构造函数
    Program(int s, int e, int i) : start(s), end(e), index(i) {}
};

// 比较函数，用于排序
bool cmp(Program& p1, Program& p2) {
    // 持续时间短的排在前面
    if (p1.end - p1.start != p2.end - p2.start) {
        return p1.end - p1.start < p2.end - p2.start;
    }
    // 如果持续时间相同，开始时间早的排在前面
    else if (p1.start != p2.start) {
        return p1.start < p2.start;
    }
    // 如果开始时间也相同，编号小的排在前面
    else {
        return p1.index < p2.index;
    }
}

std::vector<int> sortPrograms(std::vector<std::pair<int, int>>& programs) {
    std::vector<int> result;

    // 构建电视节目数组
    std::vector<Program> programList;
    for (int i = 0; i < programs.size(); i++) {
        programList.push_back(Program(programs[i].first, programs[i].second, i + 1));
    }

    // 按照比较函数进行排序
    std::sort(programList.begin(), programList.end(), cmp);

    // 将排序后的编号加入结果数组
    for (int i = 0; i < programList.size(); i++) {
        result.push_back(programList[i].index);
    }

    return result;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<std::pair<int, int>> programs;
    for (int i = 0; i < n; i++) {
        int start, end;
        std::cin >> start >> end;
        programs.push_back(std::make_pair(start, end));
    }

    std::vector<int> result = sortPrograms(programs);

    // 输出排序后的编号
    for (int i = 0; i < result.size(); i++) {
        std::cout << result[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码说明

结构体 Program: 定义了一个结构体 Program 来存储每个节目的开始时间 start，结束时间 end 和编号 index。
比较函数 cmp: 定义了一个比较函数 cmp，用于比较两个节目的排序优先级。首先比较持续时间，持续时间短的优先；如果持续时间相同，则比较开始时间，开始时间早的优先；如果开始时间也相同，则编号小的优先。
函数 sortPrograms: 该函数接收一个表示节目开始和结束时间的 pair 数组，并返回一个排序后的编号数组。函数首先将 pair 数组转换为 Program 数组，然后使用 std::sort 函数根据 cmp 函数进行排序，最后将排序后的编号加入结果数组并返回。
主函数 main: 该函数从标准输入读取节目的开始和结束时间，并调用 sortPrograms 函数进行排序，最后输出排序后的编号。

使用示例

输入：
3
1 3
2 4
1 2

输出：
3 1 2

总结

本代码实现了一个排序算法，可以根据持续时间、开始时间和编号对电视节目进行排序，并输出排序后的编号。代码清晰易懂，便于理解和使用。