题目大意：

https://codeforces.com/gym/102012/problem/H?csrf_token=c9d0191a64a241166d54a565b1615125

区间[l , r] 中有n条线 问用k种颜色最多能染多少区间  并输出区间和r - l；

∑n <= 2e6，1 <= k <= 2e5，0 <= l < r <= 1e9。

解题思路：

把N*2 个端点排序， 对端点和颜色进行入队出队操作 当颜色为空时说明这个区间满足要求，并将此线段保留到延迟染色的队伍中等待下次染色 

ac代码：

#include<bits/stdc++.h> #define sz(x) ((int)x.size()) //#define mp(x, y) make_pair(x, y) using namespace std;
typedef long long ll;
typedef pair<int, int> pii; const int MAXN = 400010; int T, n, k, col[MAXN]; struct Node{ int st, id;
    Node(){}
    Node(int _st, int _id){//方便结构体赋值 st = _st;  id = _id;
    } bool operator < (const Node &nd) const{//否则多定义一个cmd排序 if(st == nd.st) return id < nd.id; return st < nd.st;
    }
}seg[MAXN];
queue<int> rCol, rSeg; int main(){
    scanf("%d", &T); while(T --){
        scanf("%d%d", &n, &k); while(sz(rCol)) rCol.pop(); while(sz(rSeg)) rSeg.pop(); for(int i = 1; i <= n; i ++){ int l, r;
            scanf("%d%d", &l, &r);
            col[i] = 0;
            seg[i] = Node(l, i);
            seg[i + n] = Node(r, -i);
        } if(n < k){
            printf("0\n1"); for(int i = 2; i <= n; i ++)
                printf(" 1");
            printf("\n"); continue;
        }
        sort(seg + 1, seg + 2*n + 1); for(int i = 1; i <= k; i ++)
            rCol.push(i);
        ll ans = 0; for(int i = 1; i <= 2*n; i ++){ if(sz(rCol) == 0)//没有颜色可染，此端点到前个端点必满足条件 ans += seg[i].st - seg[i - 1].st; if(seg[i].id > 0){//左端点进来 if(sz(rCol)){//有颜色染色 ，没颜色放入延迟染色 int tc = rCol.front();
                    col[seg[i].id] = tc;
                    rCol.pop();
                } else rSeg.push(seg[i].id);
            } else{//右端点出去 if(col[- seg[i].id])//已经染色则归还颜色 rCol.push(col[- seg[i].id]); else//没有说明不做贡献 col[- seg[i].id] = 1;
            } while(sz(rCol) && sz(rSeg)){ int tc = rCol.front(); int ts = rSeg.front();
                rSeg.pop(); if(col[ts]) continue;//归还了颜色没有出队 col[ts] = tc;
                rCol.pop();
            }
        }
        printf("%I64d\n", ans); for(int i = 1; i <= n; i ++)
            printf("%d%c", col[i], i == n ? '\n' : ' ');
    } return 0;
}