AcWing 907. 区间覆盖
给定N个闭区间[[ai,bi]以及一个线段区间[s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出−1。
输入格式
第一行包含两个整数s和t，表示给定线段区间的两个端点。
第二行包含整数N ，表示给定区间数。
接下来N行，每行包含两个整数ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出-1。
数据范围
思路
①将所有区间按左端点从小到大排序
②从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间
选完之后将start更新成右端点的最大值 依次选择区间并更新start如果最后一次更新的start
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100010; int n; int main() { scanf("%d", &n); priority_queue<int, vector<int>, greater<int>>p; for (int i = 0; i < n; ++i) { int x; scanf("%d", &x); p.push(x); } LL res = 0; while (!p.empty()) { if (p.size() != 1) { int a = p.top(); p.pop(); int b = p.top(); p.pop(); res += (LL)a + b; p.push(a + b); } else { p.pop(); } } cout << res << endl; return 0; }
