算法通关村-----贪心面试大热门之区间问题

判断区间是否重叠

问题描述

给定一个会议时间安排数组intervals，每个会议时间都包括开始时间和结束时间,intervals[i] = [starti,endi]，请你判断一个人是否能够参加这里面的全部会议。详见leetcode252

问题分析

先将会议安排数组按照开始时间排序，判断是否有后一会议的开始时间是在前一结束时间之前，如有，则存在区间重叠，否则不存在。

代码实现

public boolean canAttendMeetings(int[][] intervals){Arrays.sort(intervals,(a,b)->a[0]-b[0]);for(int i=1;i<intervals.length;i++){if(intervals[i][0]<intervals[i-1][1]){return false;}}return true;
}

合并区间

问题描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。详见leetcode56

问题分析

创建一个与会议数组相同大小的结果数组，用于存放合并后结果。先将数组按照开始时间进行排序，将第一个会议数组元素放入结果数组中，从第二个会议元素开始，依次比较后一个会议数组元素的开始时间是否在前一会议数组结束时间之前，如是，取两者较小的开始时间作为合并后的开始时间，取两者较大的结束时间作为合并后的结束时间，放入结果数组中。

代码实现

public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)->(a[0]-b[0]));int[][] res = new int[intervals.length][2];res[0] = intervals[0];int index = 0;for(int i=1;i<intervals.length;i++){if(intervals[i][0]<=res[index][1]){int start = Math.min(intervals[i][0],res[index][0]);int end = Math.max(intervals[i][1],res[index][1]);res[index][0] = start;res[index][1] = end;}else{index++;res[index] = intervals[i];}}return Arrays.copyOf(res,index+1);
}

插入区间

问题描述

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。详见leetcode57

问题分析

给定的区间列表已经是无重叠，按照区间起始端点排序，则我们自己不需要排序了，创建一个比给定区间列表长度大1的结果数组，当区间列表的结束时间小于带插入数组的开始时间时，直接将区间列表放入结果数组。当区间列表的开始时间大于等于带插入数组的开始时间，或者区间列表的结束时间大于等于带插入数组的结束时间（即带插入数组与区间列表有重叠时），可以将区间列表先统一合并到带插入数组，直至区间列表的开始时间大于带插入数组的结束时间，将带插入数组放入结果数组，将剩余的区间列表元素也放入带插入数组。

代码实现

public int[][] insert(int[][] intervals, int[] newInterval) {if(newInterval.length ==0){return intervals;}int[][] res = new int[intervals.length+1][2];if(intervals.length==0){res[0] = newInterval;return res;}int index = 0;int i = 0;while(index<intervals.length&&intervals[index][1]<newInterval[0]){res[i] = intervals[index];index++;i++;}while(index<intervals.length&&intervals[index][0]<=newInterval[1]){newInterval[0] = Math.min(intervals[index][0],newInterval[0]);newInterval[1] = Math.max(intervals[index][1],newInterval[1]);index++;}res[i++] = newInterval;while(index<intervals.length){res[i] = intervals[index];index++;i++;}return Arrays.copyOf(res,i);
}