// 演算法：依 start 排序後單趟掃描；新段 start <= 結果中最後一段的 end 就合併，
// 否則 push_back 一個新段。Sort by start, then one pass: merge when overlapping,
// otherwise append a new interval.

#include <vector>
#include <algorithm>   // 提供 std::sort 與 std::max / provides std::sort and std::max
using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 依每個區間的 start（即 a[0]）由小到大排序
        // lambda 是匿名比較函式，告訴 sort 誰排前面
        // Sort by start (a[0]); the lambda is an inline comparator for std::sort
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] < b[0];   // a 的起點較小就排前面 / smaller start comes first
             });

        vector<vector<int>> result;  // 動態陣列，存放合併後的區間 / output, grows as needed

        for (const auto& iv : intervals) {   // range-for 逐一取出每個區間 / iterate each interval
            // 若結果為空，或目前區間 start > 最後一段的 end，代表沒重疊 → 新增
            // Empty result, or this start beyond the last end → no overlap, append
            if (result.empty() || iv[0] > result.back()[1]) {
                result.push_back(iv);        // 複製整段加到尾端 / append a copy
            } else {
                // 重疊：把最後一段的 end 延伸為兩者較大值 / overlap: extend the last end
                result.back()[1] = max(result.back()[1], iv[1]);
            }
        }

        return result;  // 回傳合併後互不重疊的區間 / return the merged, non-overlapping intervals
    }
};