🥛使用数组
使用数组来进行操作，特别[0,1][2,4]这样连在一起。却没有相交的情况
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
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
char arr[3000] = "";
vector<vector<int>> res;
for(auto x : intervals) {
memset(arr + x[0], '1' ,x[1] - x[0]);
if(arr[x[1]] != '1')
arr[x[1]] = '2';
else
arr[x[1]] = '1';
}
int count = 0, k;
for(int i = 0; i < 3000; ++i) {
if(arr[i] != '\0') {
count = 0;
for(k = i; k < 3000 && arr[k] == '1'; ++k) {
arr[k] = '\0';
++count;
}
arr[k] = '\0';
res.push_back(vector<int>{i, i + count});
}
}
return res;
}
};
|
Accepted
169/169 cases passed (20 ms)
Your runtime beats 90.61 % of cpp submissions
Your memory usage beats 5.08 % of cpp submissions (13.3 MB)
🚆排序后比较
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
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
sort(intervals.begin(), intervals.end(), [](const vector<int>& a ,const vector<int>& b){
return a[0] < b[0];
});
// for(auto x : intervals) {
// cout << x[0] << x[1] << endl;
// }
int i = 0, beg, endx, n = intervals.size();
while(i < n) {
beg = intervals[i][0];
endx = intervals[i][1];
while(i < n - 1&& intervals[i + 1][0] <= endx) {
++i;
if(intervals[i][1] > endx)
endx = intervals[i][1];
}
// cout << beg << " " << endx << endl;
res.push_back(vector<int>{beg, endx});
++i;
}
return res;
}
};
|
Accepted
169/169 cases passed (12 ms)
Your runtime beats 99.88 % of cpp submissions
Your memory usage beats 5.08 % of cpp submissions (12.7 MB)
