Cover image for Interview Classic 150 Questions P56 Merge Intervals

Interview Classic 150 Questions P56 Merge Intervals

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-11-18

init

Intervals

Problem:

P56 Merge Intervals

https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150

First sort by the left boundary of the intervals, then merge intervals from left to right in order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        vector<vector<int> > merge(vector<vector<int> > &intervals)
        {
                int i, n = intervals.size(), left, right, last_left, last_right;
                vector<vector<int> > res;
                vector<int> last;

                std::sort(intervals.begin(), intervals.end(),
                          [](vector<int> &vec1, vector<int> &vec2) { return vec1[0] < vec2[0]; });

                last = intervals[0];

                for (i = 1; i < n; i++) {
                        left = intervals[i][0];
                        right = intervals[i][1];
                        last_left = last[0];
                        last_right = last[1];

                        if (left <= last_right && right > last_right) {
                                last = { last_left, right };
                        } else if (left <= last_right && right <= last_right) {
                                continue;
                        } else if (left > last_right) {
                                res.push_back(last);
                                last = intervals[i];
                        }
                }
                res.push_back(last);
                return res;
        }
};

leetcode hot 100 rewrite

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <vector>
#include <algorithm>

using std::vector;

class Solution {
    public:
        vector<vector<int> > merge(vector<vector<int> > &intervals)
        {
                int i, n = intervals.size();

                std::sort(intervals.begin(), intervals.end(),
                          [](vector<int> &a, vector<int> &b) { return a[0] < b[0]; });

                vector<vector<int> > res;

                vector<int> last = intervals[0];

                for (i = 1; i < n; i++) {
                        vector<int> curr = intervals[i];
                        // try to merge curr and last
                        if (curr[0] >= last[0] && curr[0] <= last[1]) { // can merge
                                last = { last[0], std::max(curr[1], last[1]) };
                        } else {
                                res.push_back(last);
                                last = curr;
                        }
                }

                res.push_back(last);

                return res;
        }
};