使用cdn的网站,宣武网站建设,重庆建设工程信息安全管理,企业建站流程大家好我是苏麟 , 今天说说贪心算法的高频题目 . 大纲 区间问题判断区间是否重叠合并区间插入区间 区间问题
判断区间是否重叠
描述 :
给定一个会议时间安排的数组 intervals #xff0c;每个会议时间都会包括开始和结束的时间intervalsl[i] [start, end] #xff0c;请你…大家好我是苏麟 , 今天说说贪心算法的高频题目 . 大纲 区间问题判断区间是否重叠合并区间插入区间 区间问题
判断区间是否重叠
描述 :
给定一个会议时间安排的数组 intervals 每个会议时间都会包括开始和结束的时间intervalsl[i] [start, end] 请你判断一个人是否能够参加这里面的全部会议。
题目 ;
LeetCode 252.会议室
这题需要开会员 , 有实力的小伙伴做一下 .
分析 : 因为一个人在同一时刻只能参加一个会议因此题目实质是判断是否存在重叠区间将区间按照会议开始时间进行排序然后遍历一遍判断后面的会议开始的时候是否前面的还没有结束即可。也就是上图中如果出现重叠的部分就直接返回false即可
解析 :
class Solution {public int[][] merge(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] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
题目 :
LeetCode 56. 合并区间 :
合并区间 分析 :
为了方便理解我们将上述序列画成序列图 和上一题一样首先对区间按照起始端点进行升序排序然后逐个判断当前区间是否与前一个区间重叠如果不重叠的话将当前区间直接加入结果集反之如果重叠的话就将当前区间与前一个区间进行合并 . 这里给一个非常好的视频解析 : 合并区间 解析 :
class Solution {public int[][] merge(int[][] intervals) {if(intervals null || intervals.length 0){return new int[][]{};}Arrays.sort(intervals,(a,b) - a[0] - b[0]);Listint[] list new ArrayList();int start intervals[0][0];int end intervals[0][1];for(int[] arr : intervals){if(arr[0] end){end Math.max(end , arr[1]);}else{list.add(new int[]{start,end});start arr[0];end arr[1];}}list.add(new int[]{start,end});return list.toArray(new int[][]{});}
}插入区间
描述 :
给你一个 无重叠的 按照区间起始端点排序的区间列表。
在列表中插入一个新的区间你需要确保列表中的区间仍然有序且不重叠如果有必要的话可以合并区间。
题目 :
LeetCode 57. 插入区间:
插入区间 分析 : 本题就是上一题的再拓展本题中的区间已经按照起始端点升序排列因此我们直接遍历区间列表寻找新区间的插入位置即可。具体步骤如下:
首先将新区间左边且相离的区间加入结果集 (遍历时如果当前区间的结束位置小于新区间的开始位15置说明当前区间在新区间的左边且相离)接着判断当前区间是否与新区间重叠重叠的话就进行合并直到遍历到当前区间在新区间的右边且相离将最终合并后的新区间加入结果集最后将新区间右边且相离的区间加入结果集 这里也给一个非常好的解析视频 : 插入区间 解析 :
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {if(intervals null){return new int[][]{};}Listint[] list new ArrayList();int i 0;while(i intervals.length newInterval[0] intervals[i][1]){list.add(intervals[i]);}while(i intervals.length newInterval[1] intervals[i][0]){newInterval[0] Math.min(intervals[i][0],newInterval[0]);newInterval[1] Math.max(intervals[i][1],newInterval[1]);}list.add(newInterval);while(i intervals.length){list.add(intervals[i]);}return list.toArray(new int[][]{});}
}这期就到这里 , 下期见啊!
