The Union of k-Segments

题意翻译

```cpp 给你 n 条线段，再给你一个整数 k。如果一个点至 少被 k 条线段覆盖，那么这个点是符合条件的，如果符合条件的点可以不间断的连起来组成 一条条的线段（注：线段中间是不能有断开的），并且要求符合条件的线段数越少越好。 （注： 只有一点也可以）。 换句话说就是让你将覆盖 k 次及 k 次以上所有的区间都找出来，如果两 个区间能够合并，那么输出他们合并的结果，例如：k=1,区间[0-3],[3-5]可以合并成[0-5]，但 是 k=1,区间[0-3][4-5]，是不能合并的，因为他们两个区间没有重叠部分。 【输入格式】 第一行输入整数 n 和 k（1≤k≤n≤10^6），分别表示 n 条线段和 k 值。 接下来 n 行，每行输入整数 li，ri（-10^9≤li≤ri≤10^9），分别表示第 i 条线段的起点和 终点。这些线段可以相互重叠和交叉。 【输出格式】 第一行输入整数 m ，表示最小的区间数。 接下来 m 行，每行输入整数 aj，bj（aj≤bj），分别表示第 j 段区间的起始和末尾。输出 必须按照从小到大（从左到右）的顺序。 【输入输出样例】 样例输入 1 1 样例输入 2 2 3 2 0 5 -3 2 3 8 3 2 0 5 -3 3 3 8 样例输出 1 1 样例输出 2 2 2 0 2 3 5 1 0 5 ```

题目描述

You are given $ n $ segments on the coordinate axis Ox and the number $ k $ . The point is satisfied if it belongs to at least $ k $ segments. Find the smallest (by the number of segments) set of segments on the coordinate axis Ox which contains all satisfied points and no others.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1<=k<=n<=10^{6} $ ) — the number of segments and the value of $ k $ . The next $ n $ lines contain two integers $ l_{i},r_{i} $ ( $ -10^{9}<=l_{i}<=r_{i}<=10^{9} $ ) each — the endpoints of the $ i $ -th segment. The segments can degenerate and intersect each other. The segments are given in arbitrary order.

输出格式

First line contains integer $ m $ — the smallest number of segments. Next $ m $ lines contain two integers $ a_{j},b_{j} $ ( $ a_{j}<=b_{j} $ ) — the ends of $ j $ -th segment in the answer. The segments should be listed in the order from left to right.

输入输出样例

输入样例 #1

3 2
0 5
-3 2
3 8

输出样例 #1

2
0 2
3 5

输入样例 #2

3 2
0 5
-3 3
3 8

输出样例 #2

1
0 5