Đề bài
Cho một tập hợp các khoảng thời gian theo thứ tự bất kỳ, gộp tất cả các khoảng chồng lấn thành một và xuất kết quả chỉ chứa các khoảng loại trừ lẫn nhau (mutually exclusive intervals).
Cho tập khoảng là {{12, 14}, {11, 13}, {20, 22}, {21, 23}} thì:
- Khoảng {12, 14} và {11, 13} chồng lấn nhau do đó gộp thành {11, 14}
- Khoảng {20, 22} và {21, 23} chồng lấn nhau do đó gộp thành {20, 23}
Thuật toán
1. Sắp xếp các khoảng dựa trên thứ tự tăng dần của thời gian bắt đầu 2. Đẩy khoảng đầu tiên lên stack 3. Với mỗi khoảng thực hiện các bước sau: 3.1. Nếu khoảng hiện tại không chồng lấn với đỉnh stack, đẩy nó vào. 3.2. Nếu khoảng hiện tại chồng lấn với đỉnh stack và thời gian kết thúc của khoảng hiện tại lớn hơn đỉnh stack, cập nhật đỉnh stack với thời gian kết thúc của khoảng hiện tại. 4. Cuối cùng, stack chứa các khoảng đã gộp.
Ví dụ
#include <iostream> #include <algorithm> #include <stack> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; struct interval{ int start; int end; }; bool compareInterval(interval i1, interval i2){ return (i1.start < i2.start); } void mergeOverlappingIntervals(interval *arr, int n){ if (n <= 0) { return; } stack<interval> s; sort(arr, arr + n, compareInterval); s.push(arr[0]); for (int i = 1; i < n; ++i) { interval top = s.top(); if (top.end < arr[i].start) { s.push(arr[i]); } else if(top.end < arr[i].end) { top.end = arr[i].end; s.pop(); s.push(top); } } cout << "Merged intervals: " << endl; while (!s.empty()) { interval i = s.top(); cout << "{" << i.start << ", " << i.end << "}" << " "; s.pop(); } cout << endl; } int main(){ interval arr[] = {{12, 14}, {11, 13}, {20, 22}, {21, 23}}; mergeOverlappingIntervals(arr, SIZE(arr)); return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Merged intervals: {20, 23} {11, 14}