先排序,再合并
注意几个细节:
1.快排的时候利用填坑的思想,base是第一个坑,先从后往前填一个坑,再从前往后填一个坑最后把base放到最后一个坑,填坑时注意判断 i < j
int i = start, j = end; while(i < j) { while(j > i && v[j].start > base.start) j --; if(j > i) { v[i] = v[j]; i ++; } while(i < j && v[i].start < base.start) i ++; if( i < j) { v[j] = v[i]; j --; } } v[i] = base;
- 快排的递归注意判断start 和 end 的大小,不然可能出现 start > end 的情况
- 合并的时候为了删除元素,需要用erase,所以遍历时用iterator,intervals.erase(iter)返回下一个迭代器,end()返回的是末尾元素下一个迭代器
iter = intervals.erase(iter);