SSL大厅安排-白红宇

SSL大厅安排

阅读量：354 次

发布时间：2019-03-04

本文共 1280 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到一种方法来最大化演讲大厅的使用时间。演讲大厅需要通过选择一些预定而拒绝其他预定，以使演讲者使用时间最长。

方法思路

问题分析：我们需要尽可能多地安排演讲，使得它们之间尽可能紧密地连续进行。这是一个典型的调度问题，可以使用贪心算法或动态规划来解决。

排序演讲时间：将所有演讲按开始时间从早到晚排序，这样可以方便地找到可以连接的演讲。

动态规划：使用动态规划来记录前i个演讲的最长时间段。对于每个演讲i，计算其与前面所有可能连接的演讲j的最长时间段，更新b[i]的值。

计算最大时间：遍历所有演讲，计算每个演讲的最长时间段，并记录最终的最大时间。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      #include 
       
        using namespace std;struct f {    int l, r;};bool cmp(f a, f b) {    if (a.l != b.l)        return a.l < b.l;    return a.r < b.r;}int main() {    int n, m = 0;    cin >> n;    struct f a[1001];    for (int i = 1; i <= n; ++i) {        int l, r;        cin >> l >> r;        a[i] = {l, r};    }    sort(a + 1, a + n + 1, cmp);    int b[1001];    b[0] = 0;    for (int i = 1; i <= n; ++i) {        b[i] = a[i].r - a[i].l;        for (int j = 1; j < i; ++j) {            if (a[j].r <= a[i].l) {                if (b[j] + (a[i].r - a[i].l) > b[i]) {                    b[i] = b[j] + (a[i].r - a[i].l);                }            }        }        if (b[i] > m)            m = b[i];    }    cout << m << endl;    return 0;}