Print the intervals after overlapping in sorted manner. Given a collection of intervals, merge all the overlapping Intervals.

Print the intervals after overlapping in sorted manner

Given a collection of intervals, merge all the overlapping Intervals.
For example:
Given [1,3], [2,6], [8,10], [15,18],
return [1,6], [8,10], [15,18].
Make sure the returned intervals are sorted.

Input

2

4

1 3 2 4 6 8 9 10

4

6 8 1 9 2 4 4 7

Output

1 4 6 8 9 10

1 9

Correct Answer.Correct Answer

Execution Time:0.01

#include <bits/stdc++.h>

using namespace std;

int main() {
    //code
    int t;
    cin >> t;
    while (t--) {
        int n, x, y;
        cin >> n;
        vector < int > v, res, ans;

        for (int i = 0; i < n; ++i) {
            cin >> x >> y;
            v.push_back(x);
            res.push_back(y);
        }

        sort(v.begin(), v.end());
        sort(res.begin(), res.end());
        int i = 0, j = 0;
        ans.push_back(v[i]);
        for (i = 1; i < n; ++i) {
            if (res[j] < v[i]) {
                ans.push_back(res[j]);
                ans.push_back(v[i]);

            }
            ++j;
        }

        ans.push_back(res[n - 1]);

        for (int i = 0; i < ans.size(); i += 2) {
            cout << ans[i] << " " << ans[i + 1] << " ";
        }
        cout << endl;

    }
    return 0;
}