Gom Đoạn ETC Cao Tốc

Mô tả

Trên cao tốc Pháp Vân – Cầu Giẽ, hệ thống thu phí không dừng ETC hoạt động ở nhiều đoạn rải rác dọc tuyến. Mỗi đoạn được ghi nhận bằng hai mốc kilomet: điểm bắt đầu và điểm kết thúc (đã tính bằng số thực, đơn vị kilomet). Vì các nhà thầu lắp đặt độc lập nên nhiều đoạn chồng lấn hoặc nối tiếp nhau, tạo ra bản báo cáo bị rời rạc và trùng lặp.

Trung tâm điều hành muốn biết tổng chiều dài cao tốc thực sự được phủ sóng ETC. Nhiệm vụ của bạn là gom tất cả các đoạn chạm mút hoặc lấn vào nhau thành những cung đường liên tục, sau đó tính tổng chiều dài các cung đã gộp.

Quy tắc gộp: nếu đầu đoạn sau nhỏ hơn hoặc bằng đuôi đoạn trước thì cả hai đoạn được nối thành một cung lớn với đầu là đầu nhỏ nhất và đuôi là đuôi lớn nhất.

Đầu vào

• Một danh sách doan, mỗi phần tử là một cặp [batDau, ketThuc] (số nguyên) biểu diễn mốc đầu và mốc đuôi của một đoạn ETC. Định dạng stdin cho mã biên dịch: dòng đầu là số nguyên n (số đoạn), tiếp theo n dòng mỗi dòng ghi hai số batDau ketThuc.

Đầu ra

• Trả về một số nguyên duy nhất là tổng chiều dài cao tốc được phủ sóng sau khi gộp. Với mã biên dịch, in số nguyên đó trên một dòng.

Ràng buộc

• 1 <= n <= 10^5
• 0 <= batDau <= ketThuc <= 10^6
• Tổng chiều dài kết quả đảm bảo nhỏ hơn 2^53, không cần lo lắng tràn số khi dùng JavaScript.

Ví dụ

Giả sử danh sách các đoạn ETC là [[1, 3], [2, 6], [8, 10], [15, 18]].

• Bước 1: sắp xếp theo điểm bắt đầu tăng dần, danh sách giữ nguyên.
• Bước 2: đoạn [1, 3] và [2, 6] chồng nhau vì 2 <= 3, gộp thành [1, 6].
• Bước 3: [8, 10] rời biệt, giữ nguyên. Tương tự [15, 18] cũng rời biệt.
• Các cung cuối cùng: [1, 6] (chiều dài 5), [8, 10] (chiều dài 2), [15, 18] (chiều dài 3).
• Tổng chiều dài là 5 + 2 + 3 = 10.