题目大意

有 N 个会议（区间）和 K 个会议室。如果两个会议在未取消的情况下，通过区间重叠或传递关系相连，则它们必须放在不同的会议室。问通过取消一些会议（代价为违约金），使得剩余会议能满足会议室分配要求的最小总代价。

核心观察

1. 相关会议形成连通分量
   根据规则，相关关系具有传递性。所有未取消的会议会形成若干个连通块（连通分量）。

2. 分量独立处理
   不同连通分量之间互不影响，可以独立处理。

3. 贪心策略
   对于一个大小为 m 的连通分量：

   • 如果 m <= K，不需要取消任何会议。
   • 如果 m > K，必须取消至少 m - K 个会议。最优策略是取消该分量中违约金最小的 m - K 个会议。

算法步骤

1. 构建图并找连通分量

   • 将每个会议视为节点。
   • 如果两个会议区间重叠（max(S[i], S[j]) < min(E[i], E[j])），则连边。
   • 使用 BFS/DFS 或并查集找出所有连通分量。

2. 计算最小代价

   • 对每个连通分量：
     • 若分量大小 m <= K，代价增加 0。
     • 若 m > K，将该分量内所有会议的违约金排序，取最小的 m - K 个求和，加入总代价。

3. 返回总代价

复杂度分析

• 建图：O(N²)（判断每对区间是否重叠）
• 找连通分量：O(N²)
• 排序：每个分量内部排序，总复杂度 O(N log N)
• 总体：O(N²)，在 N <= 2500 时可行

代码实现（C++ 核心逻辑）

#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;

long long min_charge(int K, vector<int> S, vector<int> E, vector<int> W) {
    int N = S.size();
    vector<vector<int>> graph(N);
    
    // 建图
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (max(S[i], S[j]) < min(E[i], E[j])) {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }
    
    // 找连通分量
    vector<bool> visited(N, false);
    long long ans = 0;
    
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            vector<int> component;
            queue<int> q;
            q.push(i);
            visited[i] = true;
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                component.push_back(u);
                
                for (int v : graph[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            
            // 处理当前分量
            int m = component.size();
            if (m > K) {
                vector<int> weights;
                for (int idx : component) {
                    weights.push_back(W[idx]);
                }
                sort(weights.begin(), weights.end());
                for (int j = 0; j < m - K; j++) {
                    ans += weights[j];
                }
            }
        }
    }
    
    return ans;
}

关键点

• 问题本质：在区间图中，删除代价最小的顶点使得每个连通分量大小不超过 K
• 核心算法：连通分量 + 贪心
• 优化方向：对于大规模数据，可使用扫描线优化建图过程