Mô tả
Tại văn phòng FPT ở quận Cầu Giấy, anh Tâm quản lý một phòng họp nhỏ dùng chung cho toàn bộ các nhóm phát triển phần mềm. Trong ngày, rất nhiều nhóm đặt phòng theo dạng khoảng thời gian [bắt đầu, kết thúc) — nghĩa là cuộc họp bắt đầu đúng giờ bắt đầu và giải tỞa đúng giờ kết thúc. Do hệ thống đặt chỗ cũ chưa kiểm tra trùng giờ, một số cuộc họp bị xếp chồng chéo lên nhau.
Anh Tâm muốn biết: nếu chỉ nhìn vào lịch sử đặt phòng trong ngày, tổng thời gian thực tế phòng họp được sử dụng là bao nhiêu phút? Thời gian các cuộc họp chồng nhau chỉ tính một lần, vì phòng đó chỉ có một.
Nhiệm vụ của bạn: cho danh sách các khoảng thời gian đặt phòng, hãy tính tổng số phút phòng họp có ít nhất một cuộc họp đang diễn ra.
Đầu vào
- Một mảng hai chiều
lich_hen, mỗi phần tử là[bat_dau, ket_thuc]với0 <= bat_dau < ket_thuc <= 10^6(phút).
Đầu ra
- Trả về một số nguyên duy nhất: tổng số phút phòng họp được sử dụng thực tế (sau khi gộp các khoảng chồng nhau).
Ràng buộc
0 <= n <= 10^4(số lượng lịch đặt).0 <= bat_dau < ket_thuc <= 10^6.- Tổng thời gian thực tế không vượt quá
10^6phút.
Ví dụ
Ví dụ 1:
- Đầu vào:
[[1, 3], [2, 6], [8, 10], [15, 18]] - Đầu ra:
9
Giải thích từng bước:
- Sắp xếp theo giờ bắt đầu:
[1,3], [2,6], [8,10], [15,18]. - Gộp
[1,3]và[2,6](trùng) thành[1,6], cộng6 - 1 = 5phút. [8,10]rời rạc, cộng10 - 8 = 2phút.[15,18]rời rác, cộng18 - 15 = 3phút.- Tổng:
5 + 2 + 3 = 10.
(Lưu ý: kết quả đúng cho ca này là 10, hãy cẩn thận khi tính!)
Ví dụ 2:
- Đầu vào:
[[1, 4], [4, 5]] - Đầu ra:
4
Giải thích: Hai khoảng [1,4) và [4,5) nối tiếp nhau tại thời điểm 4, không chồng lấn. Tổng thời gian là (4-1) + (5-4) = 4 phút.