$贪心$
$按左端点排序。$
$当我们钦定了最右的左端点，那么自然希望右端点尽量靠右$
$考虑之前的区间，那么我们相当于选之前的区间中第k大的右端点$
$堆维护一下就可以了，每次把新的元素放进堆，如果能更新就弹出旧的，否则弹出自己$
#include<cstdio> #include<cstring> #include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; const int N = 1e6 + 5; int n, k, ans; struct data {int l, r, id;bool friend operator < (const data &a, const data &b) {return a.l < b.l;} } a[N]; priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q; int main() { // freopen("1.in", "r", stdin);scanf("%d%d", &n, &k);for(int i = 1; i <= n; ++i) {scanf("%d%d", &a[i].l, &a[i].r);a[i].id = i;}sort(a + 1, a + n + 1);for(int i = 1; i < k; ++i) {q.push(make_pair(a[i].r, a[i].id));}for(int i = k; i <= n; ++i) {q.push(make_pair(a[i].r, a[i].id));ans = max(ans, q.top().first - a[i].l);q.pop();}printf("%d\n", ans);while(!q.empty()) {q.pop();}for(int i = 1; i < k; ++i) {q.push(make_pair(a[i].r, a[i].id));}for(int i = k; i <= n; ++i) {q.push(make_pair(a[i].r, a[i].id));if(ans == q.top().first - a[i].l) {vector<int> v;while(!q.empty()) {v.push_back(q.top().second);q.pop();}sort(v.begin(), v.end());for(int i = 0; i < v.size(); ++i) {printf("%d ", v[i]);}return 0;}q.pop();}return 0; }