Merge Intervals@LeetCode
文章目录
Merge Intervals
这也是一题我有点不太能理解为什么可以标为hard的题目。解法其实很直观,就是先对interval进行排序,然后遍历一遍。这里需要注意的点有两个:
对
interval进行排序需要构造一个比较器。在遍历过程中,如果结果集合为空或者当前
interval与结果集合中的最后一个interval不重叠,那么就直接将当前interval直接加入到结果集合中;如果发生了重叠,那么将结果集合的最后一个interval的右端点改为当前interval的右端点。
实现代码:
javapublic class Solution { public List<Interval> merge(List<Interval> intervals) { List<Interval> result = new ArrayList<Interval>(); Comparator<Interval> comparator = new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { if (o1.start == o2.start) { return o1.end - o2.end; } return o1.start - o2.start; } }; Collections.sort(intervals, comparator); for (Interval interval : intervals) { int last = result.size(); if (last == 0 || result.get(last - 1).end < interval.start) { Interval newInterval = new Interval(interval.start, interval.end); result.add(newInterval); } else { result.get(last - 1).end = Math.max(interval.end, result.get(last - 1).end); } } return result; } }
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论