Cho một mảng các khoảng thời gian intervals, trong đó intervals[i] = [start_i, end_i]. Hãy hợp nhất tất cả các khoảng bị chồng lấn và trả về mảng các khoảng không chồng lấn.
Ví dụ 1: intervals = [[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]] (vì [1,3] và [2,6] chồng lấn thành [1,6]).
Định Dạng Đầu Vào (Input)
Một dòng chứa mảng 2D intervals
Định Dạng Đầu Ra (Output)
Mảng 2D các khoảng đã hợp nhất
Ràng Buộc (Constraints)
1 <= intervals.length <= 10^4
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[[1,3],[2,6],[8,10],[15,18]]
Output:
[[1,6],[8,10],[15,18]]
Giải thích: [1,3] và [2,6] gộp thành [1,6]
Ví dụ 2:
Input:
[[1,4],[4,5]]
Output:
[[1,5]]
Giải thích: Đầu mút trùng nhau [1,5]
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Sắp Xếp & Hợp Nhất O(n log n)
Sắp xếp các khoảng theo thời điểm bắt đầu start. Duyệt qua từng khoảng: Nếu khoảng hiện tại chồng lấn với khoảng trước (start <= prev.end), mở rộng prev.end = max(prev.end, end). Ngược lại thêm khoảng mới.
Dữ liệu đầu vào (Input):
[[1,3],[2,6],[8,10],[15,18]]
Kết quả kỳ vọng (Expected Output):
[[1,6],[8,10],[15,18]]
Dữ liệu đầu vào (Input):
[[1,4],[4,5]]
Kết quả kỳ vọng (Expected Output):
[[1,5]]
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
