题解 | 区间覆盖问题的变形

时间复杂度：O(mlogm)

区间覆盖问题

给定n个小区间和一个范围[a, b],选择尽量少的区间，使得[a, b]能够被完全覆盖。

解法：贪心

如果有区间x和y，x包含了y，显然选择x这个大区间更好。

因此考虑对每个区间按左端点升序排序，从第一个小区间开始选择，每次选择区间左端点在目标区间内且右端点尽可能大的区间。每次选择区间后更新目标区间（左端点更新为选中区间的右端点+1）。

排序开销：O(nlogn)

选区间开销：O(n)

总时间复杂度：O(nlogn)

区间预处理

显然，本题没有明说各个小区间，因此需要预处理出小区间。

我们可以把m个请求服务器看成[0,m-1]的区间。

每个代理服务器在需要切换之前（后）看成小区间。

如请求服务器顺序为ABBA，那么A对应的小区间有[1,2],B对应的小区间有[0,0]、[3,3]

源码

//
// Created by Zed on 2024/1/22.
//
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <map>

using namespace std;
const int MAXN = 1e3 + 100;

struct Interval {
    int a, b;

    bool operator<(const Interval interval) {
        if (a != interval.a) {
            return a < interval.a;
        }
        return b > interval.b;
    }
} intervals[MAXN];


int main() {
    int n, m;
    while (cin >> n) {
        map<string, int> dict;//维护上一次IP出现的下标
        for (int i = 0; i < n; ++i) {
            string tmp;
            cin >> tmp;
            dict[tmp] = -1;
        }
        int cnt = 0;//区间数
        cin >> m;
        for (int i = 0; i < m; ++i) {
            string tmp;
            cin >> tmp;
            if (dict.count(tmp)) {
                if (i - 1 >= dict[tmp] + 1) {
                    intervals[cnt].a = dict[tmp] + 1;
                    intervals[cnt].b = i - 1;//不包含端点
                    cnt++;
                }
                dict[tmp] = i;
            }
        }
        for (const auto &item: dict) {
            if (m - 1 >= item.second + 1) {
                intervals[cnt].a = item.second + 1;
                intervals[cnt].b = m - 1;//不包含端点
                cnt++;
            }
        }
        sort(intervals, intervals + cnt);
        int ans = -1;
        int l = 0;
        int j = 0;
        while (l <= m - 1 && j < cnt) {
            if (intervals[j].a > l) {
                ans = -1;
                break;
            }
            int tmp_l = l;
            while (j < cnt && intervals[j].a <= l) {
                tmp_l = max(intervals[j].b + 1, tmp_l);
                j++;
            }
            l = tmp_l;
            ans++;
        }
        cout << ans << endl;
    }
}