[HackerRank] Merge and Sort Intervals

Merge and Sort Intervals

Difficulty: Medium

Given an array of intervals [startTime, endTime], merge all overlapping intervals and return a sorted array of non-overlapping intervals.

Example

Input

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

Output

[[1, 6], [8, 10], [15, 18]]

Explanation

- Step 1: Sort intervals by start time (already sorted). 
- Step 2: Initialize merged list with first interval [1,3]. 
- Step 3: Compare [2,6] with last merged [1,3]. They overlap (2 ≤ 3), so merge into [1,6]. Step 4: Compare [8,10] with last merged [1,6]. No overlap (8 > 6), append [8,10]. 
- Step 5: Compare [15,18] with last merged [8,10]. No overlap (15 > 10), append [15,18]. 

Result: [[1,6],[8,10],[15,18]].

Input Format

• The first line contains an integer denoting the number of intervals.
• The second line contains an integer denoting the length of individual interval array.
• Each of the next N lines contains two space-separated integers startTime and endTime
• Intervals may be provided in any order; duplicates and fully contained intervals are allowed.

Example

4
2
1 3
2 6
8 10
15 18

here, 4 is the number of intervals, 2 is the length of individual interval array, followed by the intervals.

Constraints

• 0 <= intervals.length <= 100000
• intervals[i].length == 2 for all 0 <= i < intervals.length
• 0 <= intervals[i][0] < intervals[i][1] <= 10^9 for all 0 <= i < intervals.length

Output Format

• Return a 2D array of two space-separated integers start and end, representing the merged intervals sorted by increasing start time.

Sample Input 0

0
0

Sample Input 1

1
2
5 10

Sample Output 1

5 10

Consideration:

1. Sorting the intervals by each element's startTime.

2. Check if the previous interval overlapped the current interval.

3. Going to the next interval.

Code:

 /*

 * Complete the 'mergeHighDefinitionIntervals' function below.

 *

 * The function is expected to return a 2D_INTEGER_ARRAY.

 * The function accepts 2D_INTEGER_ARRAY intervals as parameter.

 */

vector<vector<int>> mergeHighDefinitionIntervals(vector<vector<int>> intervals) {

    int n = intervals.size();

    vector<vector<int>> outIntervals;

    if (n == 0) return {{}};

    //sort first.

    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {

        return a[0] < b[0]; // Sort by start_time

    });

   

    outIntervals.push_back(intervals[0]);

    for (int i=1;i<n;i++) {

        if (outIntervals.back()[1] >= intervals[i][0]) {

            if (outIntervals.back()[1] < intervals[i][1]) {

                outIntervals.back()[1] = intervals[i][1];

            }

        }

        else {

            outIntervals.push_back(intervals[i]);

        }

    }

    return outIntervals;

}