codekofi
← All questions

Non-overlapping Intervals

HardIntervals

The problem

Return the fewest intervals you would have to remove so that none of the remaining ones overlap. Intervals that merely touch do not overlap.

eraseOverlapIntervals({{1,2},{2,3},{3,4},{1,3}})

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.

1int eraseOverlapIntervals(vector<vector<int>> intervals) {
2
3 if (!(intervals.empty())) {
4 return 0;
5 }
6
7 sort(intervals.begin(), intervals.end(),
8 [](const vector<int>& a, const vector<int>& b) {
9 return a[1] < b[1];
10 });
11
12 int kept = 1;
13 int edge = INT_MIN;
14
15 for (const auto& s : intervals) {
16
17 if (s[0] >= edge) {
18 kept++;
19 edge = s[1];
20 }
21 }
22
23 int total = intervals.size();
24
25 return total - kept;
26}
1int eraseOverlapIntervals(vector<vector<int>> intervals) {
2
3 if (intervals.empty()) {
4 return 0;
5 }
6
7 sort(intervals.begin(), intervals.end(),
8 [](const vector<int>& a, const vector<int>& b) {
9 return a[1] < b[1];
10 });
11
12 int kept = 0;
13 int edge = INT_MIN;
14
15 for (const auto& s : intervals) {
16
17 if (s[0] >= edge) {
18 kept++;
19 edge = s[1];
20 }
21 }
22
23 int total = intervals.size();
24
25 return total - kept;
26}
1int eraseOverlapIntervals(vector<vector<int>> intervals) {
2
3 if (!(intervals.empty())) {
4 return 0;
5 }
6
7 sort(intervals.begin(), intervals.end(),
8 [](const vector<int>& a, const vector<int>& b) {
9 return a[1] < b[1];
10 });
11
12 int kept = 0;
13 int edge = INT_MIN;
14
15 for (const auto& s : intervals) {
16
17 if (!(s[0] >= edge)) {
18 kept++;
19 edge = s[1];
20 }
21 }
22
23 int total = intervals.size();
24
25 return total - kept;
26}