From MergeIntervals to list and vector iterator
这个是之前做过的题目，但是再做发现还是要花很多时间，花时间的原因：
- 忘记是start 还是end排序，然后想再证明发现不会了，猜了end，结果挂了
- 若不单独考察链表操作时用list，但是list的bidirectional的iterator爆难用，由于不能随机访问，所以iterator只能++ — 不能+1 -1, ++之后还会修改iterator值，要特别当心，
另外vector和list的 插入 insert 删除 erase 都只能用iterator，所以即使vector要插入删除也要用迭代器遍历，vector删除不需要记录下返回的迭代器，因为内存是连续的，
直接迭代器加1都可以的，但是list可能就不行了，因为删除了*it, it就回不到链表上了，erase返回的iterator是删除之后的第一个元素的指针，所以for的时候++ 要特别当心不要移动过了，
如果— 然后再中和掉for的++ 有风险，如果一开始指向begin可能就会越界了，所以最好是for不写++ 这个分支也不— 而在另一个分支++ - 一开始觉得vector删除会大量移动元素，估计比list慢，但是不确定慢多少，后来测试确实TLE了，估算下，移动元素上限是n-2+…+1, O(n^2)，linklist利用链表删除高效，每次操作都是O(1),总复杂度O(n)。
- sort内嵌的comp函数再次忘记写成静态成员函数，今天想通了似乎，写的每个solution class里的函数都是成员函数，实际都是
solution的instance来调用的，而sort内嵌的comp函数则不允许这样的类型，所以写成静态成员函数，是整个class一份的成员函数。同时comp函数还没有仔细
考虑多种case，如果start相同的怎么办，这个也是需要处理的，不然可能是出现start相同，结果end大的再前面，这样merge可能会有问题。 - 分析interval merge 情况的时候比较慢，主要就是三类情况，关键是怎么设计if else 嵌套来分类
第一次写的自己控制linklist的mergeintervals，还比较青涩o(╯□╰)o：
struct Node
{
Interval interval;
Node* next;
};
class Solution {
public:
static bool SortComp(const Interval& T1, const Interval&T2)
{
return T1.start<T2.start;
}
Node* CreateLinkList(vector<Interval> data)
{
Node* head=NULL;
head=new Node();
head->interval=data[0];
head->next=NULL;
Node* rail=head,*p;// record each rail
for(int i=1;i<data.size();i++)
{
p=new Node();
p->interval=data[i];
p->next=NULL;
rail->next=p;
rail=rail->next;
}
return head;
}
bool ShouldMerge(Interval n1,Interval n2, Interval& mergedn)
{
if(n1.start<=n2.start&&n2.start<=n1.end&&n1.end<=n2.end)//intersect
{
mergedn.start=n1.start;
mergedn.end=n2.end;
return true;
}
if(n1.start<=n2.start&&n2.end<=n1.end)//subset of another
{
mergedn.start=n1.start;
mergedn.end=n1.end;
return true;
}
return false;
}
vector<Interval> merge(vector<Interval> &intervals)
{
if(intervals.size()<=1) return intervals;
sort(intervals.begin(),intervals.end(),SortComp);//start sort descending, for vector pop_back
Node* head=CreateLinkList(intervals);
//merge interval with linklist
Node* p=head;
while(p->next!=NULL)//at least two node initially
{
Interval mergedn;
if( ShouldMerge(p->interval,p->next->interval,mergedn) || ShouldMerge(p->next->interval,p->interval,mergedn) )
{
//delete p, p->next;
//insert mergedn;
p->interval=mergedn;
p->next=p->next->next;
}
else
p=p->next;
}
/*
for(int i=0;i<intervals.size()-1;i++)
{
Interval mergedn;
if(ShouldMerge(intervals.at(i),intervals.at(i+1),mergedn)|| ShouldMerge(intervals.at(i+1),intervals.at(i),mergedn))
{
intervals.erase(intervals.begin()+i);
intervals.at(i)=mergedn;
//intervals.erase(intervals.begin()+i);
//intervals.insert(intervals.begin()+i,mergedn);
i--;
}
else
;
}*/
//copy linklist to vector
p=head;
intervals.clear();
while(p!=NULL)
{
intervals.push_back(p->interval);
p=p->next;
}
return intervals;
}
};
基于vector的mergeinterval：
static bool IntComp(Interval i1,Interval i2)//end ascending
{
if(i1.start<i2.start)
return true;
else if(i1.start>i2.start)
return false;
else
{
if(i1.end<i2.end)
return true;
else
return false;
}
}
bool MergeInterval(Interval i1, Interval i2, Interval& newi)
{
if(i1.end < i2.start)
return false;
else if(i1.end<=i2.end){
newi.start=i1.start;newi.end=i2.end;return true;}
else if(i1.end>i2.end)
{
newi.start=i1.start;
newi.end=i1.end;
return true;
}
}
vector<Interval> merge(vector<Interval> &intervals)
{
sort(intervals.begin(),intervals.end(),IntComp);
list<Interval> lis;
for(int i=0;i<intervals.size();i++)
lis.push_back(intervals[i]);
for(list<Interval>::iterator it=lis.begin();it!=lis.end();)
{
Interval i1,i2,newi;
i1=*it;
it++;
if(it==lis.end()) break;
i2=*it;
if(MergeInterval(i1,i2,newi))
{
*it=newi;
it--;
it=lis.erase(it);
}
}
intervals.clear();
//int i=0;
for(list<Interval>::iterator it=lis.begin();it!=lis.end();it++)
intervals.push_back(*it);
return intervals;
}
基于list的mergeintervals(IntComp,MergeInterval函数同vector的)：
vector<Interval> merge(vector<Interval> &intervals)
{
sort(intervals.begin(),intervals.end(),IntComp);
list<Interval> lis;
for(int i=0;i<intervals.size();i++)
lis.push_back(intervals[i]);
for(list<Interval>::iterator it=lis.begin();it!=lis.end();)
{
Interval i1,i2,newi;
i1=*it;
it++;
if(it==lis.end()) break;
i2=*it;
if(MergeInterval(i1,i2,newi))
{
*it=newi;
it--;
it=lis.erase(it);
}
}
intervals.clear();
//int i=0;
for(list<Interval>::iterator it=lis.begin();it!=lis.end();it++)
intervals.push_back(*it);
return intervals;
}
附上之前的解题报告 http://blog.csdn.net/richardzrc/article/details/31454199
学到一个阿三的短语，get a life, 享受生活