整体不是很难。
一开始超时了,主要是由于要不停维护state这张表格，耗费时间。因此修改为区间处理。
class Solution {public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { if(timeSeries.size()==0) return 0; else { vector<int> state(timeSeries[timeSeries.size()-1]+duration,0); int poisonedTime=0; for(int i=0;i<timeSeries.size();i++) { for(int j=timeSeries[i];j<timeSeries[i]+duration;j++) { if(state[j]==0) { poisonedTime++; state[j]=1; } } cout<<poisonedTime<<endl; } return poisonedTime; } }};正确代码： 采用区间的greedy策略，将每一个小区间按照pair的第一维排序，然后建立一个queue维护，计算区间之间1的个数，得到最后的结果。
queue处理时要细心。
class Solution {public: static bool cmp( pair<int,int>& a, pair<int,int>& b) { if(a.first<b.first) return true; else return false; } int findPoisonedDuration(vector<int>& timeSeries, int duration) { if(timeSeries.size()==0) return 0; else { vector<pair<int, int>> range; for(int i=0;i<timeSeries.size();i++) { pair<int, int> temp(timeSeries[i],timeSeries[i]+duration-1); range.push_back(temp); } sort(range.begin(),range.end(),cmp); //PRocess range /*for(int i=0;i<range.size();i++) cout<<range[i].first<< " "<<range[i].second<<endl; */ int poisonedTime=0; queue<pair<int,int>> findRange; for(int i=0;i<range.size();i++) { if(!findRange.empty()) { if(findRange.back().second>=range[i].first) { pair<int,int> newPair(findRange.back().first,range[i].second); findRange.push(newPair); findRange.pop(); } else { poisonedTime+=findRange.front().second-findRange.front().first+1; findRange.push(range[i]); findRange.pop(); } } else findRange.push(range[i]); //cout<<findRange.size()<<endl; /*for(int i=0;i<findRange.size();i++) cout<<findRange.back().first<< " "<<findRange.back().second<<endl;*/ } if(!findRange.empty()) poisonedTime+=findRange.front().second-findRange.front().first+1; return poisonedTime; } }};新闻热点
疑难解答
