网站视频建设,莆田百度seo公司,中国交通建设网官方网站,科技公司网页设计欣赏整体不难#xff0c;一开始以为是线段树#xff0c;后来仔细看来不需要#xff0c;从左到右扫#xff0c;判断是否要merge就是了。此题有几个要注意的地方#xff1a;1.Java的Comparator要会写#xff1b;2.循环结束后的ans.add(tmp)不要忘记#xff1b;3.merge的时候一开始以为是线段树后来仔细看来不需要从左到右扫判断是否要merge就是了。此题有几个要注意的地方1.Java的Comparator要会写2.循环结束后的ans.add(tmp)不要忘记3.merge的时候左右边界要计算一下。 /*** Definition for an interval.* public class Interval {* int start;* int end;* Interval() { start 0; end 0; }* Interval(int s, int e) { start s; end e; }* }*/
public class Solution {public ArrayListInterval merge(ArrayListInterval intervals) {// Start typing your Java solution below// DO NOT write main() function int len intervals.size();if (len 0 || len 1) return intervals;ArrayListInterval ans new ArrayListInterval();Collections.sort(intervals, new IntervalComparator());Interval tmp intervals.get(0);for (int i 1; i len; i) {Interval itv intervals.get(i);if (tmp.end itv.start) { // mergeableint left Math.min(tmp.start, itv.start);int right Math.max(tmp.end, itv.end);tmp new Interval(left, right);}else {ans.add(tmp);tmp intervals.get(i);}}ans.add(tmp);return ans;}
}class IntervalComparator implements ComparatorInterval
{public int compare(Interval a, Interval b) {return a.start - b.start;}
}第二刷 bool cmp(const Interval a, const Interval b)
{if (a.start ! b.start)return a.start b.start;elsereturn a.end b.end;
}class Solution {
public:vectorInterval merge(vectorInterval intervals) {vectorInterval result;sort(intervals.begin(),intervals.end(), cmp);for (int i 0; i intervals.size(); i){if (result.size() 0 || result.back().end intervals[i].start){result.push_back(intervals[i]);}else if (intervals[i].end result.back().end){result.back().end intervals[i].end;}}return result;}
};转载于:https://www.cnblogs.com/lautsie/p/3254191.html
