机场廊桥分配问题：优化算法实现最大化飞机停靠数量

算法优化：机场廊桥分配问题

当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。

机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。

L 市新建了一座机场，一共有 n 个廊桥。该机场决定，廊桥的使用遵循'先到先得'的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻，请你负责将 n 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。

输入描述

从文件 airport.in 中读入数据。输入的第一行包含 3 个正整数 n, m1, m2 分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。接下来 m1 行是国内航班的信息，第 i 行包含 2 个正整数 a1,i, b1,i，分别表示一架国内航班飞机的抵达、离开时刻。接下来 m2 行是国际航班的信息，第 i 行包含 2 个正整数 a2,i, b2,i，分别表示一架国际航班飞机的抵达、离开时刻。每行的多个整数由空格分隔。

输出描述

输出到文件 airport.out 中。输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。

样例1

输入

输出

样例2

输入

输出

代码实现 (C++)

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

using namespace std;

struct Flight {
    int arrival;
    int departure;
    int type; // 1: domestic, 2: international
};

bool compare(Flight f1, Flight f2) {
    return f1.arrival < f2.arrival;
}

int main() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    
    vector<Flight> domesticFlights(m1);
    vector<Flight> internationalFlights(m2);
    
    for (int i = 0; i < m1; i++) {
        cin >> domesticFlights[i].arrival >> domesticFlights[i].departure;
        domesticFlights[i].type = 1;
    }
    
    for (int i = 0; i < m2; i++) {
        cin >> internationalFlights[i].arrival >> internationalFlights[i].departure;
        internationalFlights[i].type = 2;
    }
    
    sort(domesticFlights.begin(), domesticFlights.end(), compare);
    sort(internationalFlights.begin(), internationalFlights.end(), compare);
    
    vector<int> gates(n); // gates[0]: domestic gates, gates[1]: international gates
    int maxGates = 0;
    int maxGatesCount = 0;
    
    int dIndex = 0;
    int iIndex = 0;
    
    while (dIndex < m1 && iIndex < m2) {
        if (domesticFlights[dIndex].arrival < internationalFlights[iIndex].arrival) {
            if (gates[domesticFlights[dIndex].type - 1] > 0) {
                gates[domesticFlights[dIndex].type - 1]--;
                maxGatesCount++;
            }
            gates[0]++;
            dIndex++;
        } else {
            if (gates[internationalFlights[iIndex].type - 1] > 0) {
                gates[internationalFlights[iIndex].type - 1]--;
                maxGatesCount++;
            }
            gates[1]++;
            iIndex++;
        }
        maxGates = max(maxGates, maxGatesCount);
    }
    
    while (dIndex < m1) {
        if (gates[domesticFlights[dIndex].type - 1] > 0) {
            gates[domesticFlights[dIndex].type - 1]--;
            maxGatesCount++;
        }
        gates[0]++;
        dIndex++;
        maxGates = max(maxGates, maxGatesCount);
    }
    
    while (iIndex < m2) {
        if (gates[internationalFlights[iIndex].type - 1] > 0) {
            gates[internationalFlights[iIndex].type - 1]--;
            maxGatesCount++;
        }
        gates[1]++;
        iIndex++;
        maxGates = max(maxGates, maxGatesCount);
    }
    
    cout << maxGates << endl;
    
    return 0;
}

算法解释

该算法使用贪心策略，按照飞机抵达时间顺序进行处理。对于每架飞机，如果其所属区域还有空闲的廊桥，则分配廊桥；否则停靠在远机位。

具体实现：

首先将国内航班和国际航班信息分别存储在两个数组中，并按抵达时间进行排序。
使用两个指针分别指向国内航班数组和国际航班数组的开头。
比较两个指针指向的航班的抵达时间，选择抵达时间较早的航班进行处理。
如果该航班所属区域还有空闲的廊桥，则分配廊桥，并更新廊桥数量和已停靠廊桥的飞机数量。
否则，该航班只能停靠远机位。
循环以上步骤，直到所有航班都被处理。

优化

该算法的时间复杂度为 O(m1 + m2)，其中 m1 和 m2 分别表示国内航班和国际航班的数量。算法中使用两个指针分别指向国内航班数组和国际航班数组的开头，这样可以避免对整个数组进行遍历，从而提高效率。

总结

本题使用贪心算法，根据飞机抵达时间和廊桥可用情况，合理分配廊桥资源，实现效益最大化。该算法简单易懂，且时间复杂度较低，适用于解决类似的资源分配问题。