‹ 上一题下一题 ›

j01286. 合并区间未做

1000 ms 256 MB 测试点 10 通过率 29% J-29·贪心 J·算法自拟题贪心

文件读写输入j01286.in输出j01286.out

题目描述

给出 $n$ 个区间，把所有相交或端点相触的区间合并成大区间。输出合并后的区间个数，以及每个合并后的区间（按左端点升序）。

输入格式

第一行一个整数 $n$ ；接下来 $n$ 行，每行两个整数 $l_{i}, r_{i}$ 。

输出格式

第一行一个整数 $m$ ：合并后的区间个数；接下来 $m$ 行，每行两个整数，表示合并后的区间（按左端点升序）。

样例

输入

输出

数据范围

$1 \leq n \leq 2 \times 1 0^{5}$ ， $0 \leq l_{i} \leq r_{i} \leq 1 0^{9}$

输入

输出

答案