本文主要是介绍【LeetCode】Merge Intervals Insert Interval，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、Merge IntervalsTotal Accepted: 6989 Total Submissions: 34958 My Submissions
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
注意给的区间可能是无序的，先排序后处理。
基本的思路还是比较合并吧，比较考察思维逻辑，注意边界处理。
Java AC
/*** 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) {if(intervals == null){return intervals;}int size = intervals.size();if(size == 0 || size == 1){return intervals;}Collections.sort(intervals, new Comparator<Interval>() {public int compare(Interval o1, Interval o2) {if (o1.start == o2.start) {return o1.end - o2.end;}return o1.start - o2.start;}});ArrayList<Interval> list = new ArrayList<Interval>();Interval interval = intervals.get(0);int start = interval.start;int end = interval.end;for(int i = 1; i < size; i++){Interval intval = intervals.get(i);if(intval.start <= end){int tempSize = list.size();if (tempSize > 0) {list.remove(tempSize-1);}start = Math.min(start, intval.start);end = Math.max(end, intval.end);}else{if (i == 1) {list.add(new Interval(start, end));}start = intval.start;end = intval.end;}list.add(new Interval(start, end));}return list;}
}Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
求解给定的区间在已知区间的位置，将给定区间放入已知区间，然后就回到1的处理方式。
Java AC
/*** 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 ArrayList<Interval> insert(ArrayList<Interval> intervals,Interval newInterval) {ArrayList<Interval> list = new ArrayList<Interval>();if (intervals == null || intervals.size() == 0) {list.add(newInterval);return list;}int pos = searchInsert(intervals, newInterval.start);return merge(intervals, pos, newInterval);}public ArrayList<Interval> merge(ArrayList<Interval> intervals, int pos, Interval newInterval) {if(intervals == null){return intervals;}int size = intervals.size();ArrayList<Interval> newList = new ArrayList<Interval>();if (pos == 0) {newList.add(newInterval);newList.addAll(intervals);}else if (pos == size) {newList.addAll(intervals);newList.add(newInterval);}else {int i = 0;while (i < size) {if (i == pos) {newList.add(newInterval);}newList.add(intervals.get(i));i++;}}return merge(newList);}public ArrayList<Interval> merge(ArrayList<Interval> intervals) {int size = intervals.size();ArrayList<Interval> list = new ArrayList<Interval>();Interval interval = intervals.get(0);int start = interval.start;int end = interval.end;for(int i = 1; i < size; i++){Interval intval = intervals.get(i);if(intval.start <= end){int tempSize = list.size();if (tempSize > 0) {list.remove(tempSize-1);}start = Math.min(start, intval.start);end = Math.max(end, intval.end);}else{if (i == 1) {list.add(new Interval(start, end));}start = intval.start;end = intval.end;}list.add(new Interval(start, end));}return list;}public int searchInsert(ArrayList<Interval> intervals, int target) {int size = intervals.size();if (target < intervals.get(0).start) {return 0;}if (target > intervals.get(size - 1).end) {return size;}int low = 0;int high = size - 1;int mid = 0;while (low <= high) {mid = (low + high) >> 1;if (intervals.get(mid).start > target) {high = mid - 1;} else if (intervals.get(mid).start < target) {low = mid + 1;} else {return mid;}}return low;}
}这篇关于【LeetCode】Merge Intervals Insert Interval的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
