codekofi
← All questions

Merge Intervals

HardIntervals

The problem

Given a list of intervals, merge every group that overlaps and return the result. Intervals that merely touch — one ending where the next begins — count as overlapping.

merge({{1,3},{2,6},{8,10},{15,18}})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1vector<vector<int>> merge(vector<vector<int>> intervals) {
2
3 if (intervals.empty()) {
4 return {};
5 }
6
7 sort(intervals.begin(), intervals.end());
8
9 vector<vector<int>> ans;
10
11 int start = intervals[0][0];
12 int end = intervals[0][1];
13
14 for (int i = 1; i < (int)intervals.size(); i++) {
15
16 if (intervals[i][0] <= end) {
17 end = max(end, intervals[i][1]);
18 } else {
19 ans.push_back({start, end});
20 start = intervals[i][0];
21 end = intervals[i][1];
22 }
23 }
24
25 ans.push_back({start, end});
26
27 return ans;
28}
1vector<vector<int>> merge(vector<vector<int>> intervals) {
2
3 if (intervals.empty()) {
4 return {};
5 }
6
7 sort(intervals.begin(), intervals.end());
8
9 vector<vector<int>> ans;
10
11 int start = intervals[0][0];
12 int end = intervals[0][1];
13
14 for (int i = 1; i < (int)intervals.size(); i++) {
15
16 if (intervals[i][0] < end) {
17 end = max(end, intervals[i][1]);
18 } else {
19 ans.push_back({start, end});
20 start = intervals[i - 1][0];
21 end = intervals[i][1];
22 }
23 }
24
25 ans.push_back({start, end});
26
27 return ans;
28}
1vector<vector<int>> merge(vector<vector<int>> intervals) {
2
3 if (intervals.empty()) {
4 return {};
5 }
6
7 sort(intervals.begin(), intervals.end());
8
9 vector<vector<int>> ans;
10
11 int start = intervals[0][0];
12 int end = intervals[0][1];
13
14 for (int i = 1; i < (int)intervals.size(); i++) {
15
16 if (intervals[i][0] < end) {
17 end = max(end, intervals[i][1]);
18 } else {
19 ans.push_back({start, end});
20 start = intervals[i][0];
21 end = intervals[i - 1][1];
22 }
23 }
24
25 ans.push_back({start, end});
26
27 return ans;
28}