Gộp các khoảng chồng nhau

Trung bình

sắp xếpkhoảng6 test · 3 giây

Cho n khoảng đóng [l, r]. Gộp mọi khoảng chồng nhau hoặc chạm nhau (vd [1,3] và [3,5] → [1,5]), in các khoảng kết quả theo thứ tự tăng dần.

Dữ liệu vào

Dòng 1: n (1 ≤ n ≤ 10⁵).

n dòng: l r (0 ≤ l ≤ r ≤ 10⁹).

Dòng 1: số khoảng sau khi gộp. Mỗi dòng tiếp: l r.

Input

Output

Input

2
1 4
4 5

Output

1
1 5

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.