LeetCode 57. Insert Interval和 218. The Skyline Problem

港控/mmm° 2023-10-04 12:04 26阅读 0赞

## [LeetCode 57. Insert Interval][] ##

1.  学习了[力扣中国官方给出的思路][Link 1]。有：如果两个线段之间没有交集，其充要条件为r1<l2。  
    ![在这里插入图片描述][20210428111324358.png]  
    本题可转化为求线段之间的并集。
2.  另外，有一人提出了[分成 3 个阶段考察的思路][3]：用指针去扫 intervals，最多可能有三个阶段：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzMjA0NTU3_size_16_color_FFFFFF_t_70]不重叠的绿区间，在蓝区间的左边  
    有重叠的绿区间  
    不重叠的绿区间，在蓝区间的右边

[ac代码][ac]：

class Solution {
        
        public int[][] insert(int[][] intervals, int[] newInterval) {
        
        	List<int[]> ans = new ArrayList<>();
        	int i=0;
        	for(;i<intervals.length && intervals[i][1]<newInterval[0];++i) {
        
        		ans.add(intervals[i]);
        	}
        	int midLeft=newInterval[0],midR=newInterval[1];
        	for(;i<intervals.length && intervals[i][0]<=newInterval[1];++i) {
        
        		midLeft = Math.min(midLeft, intervals[i][0]);
        		midR =  Math.max(midR, intervals[i][1]);
        	}
        	ans.add(new int[] {
        midLeft,midR});
        	for(;i<intervals.length;++i) {
        
        		ans.add(intervals[i]);
        	}
        	return ans.toArray(new int[0][]);
        }
    }

## [218. The Skyline Problem][] ##

我的思路：可以把地面也看成高度为0的线段，题目转化为求线段相交。而且用新的线段newb遍历已生成的所有线段时,newb的任何部分都会与原有的某线段相交。另外有一点值得注意，因为题目要求是输出左边端点，所以我们定义本题的线段与上题不同，是左闭右开的，所以判断是否相交的标准也与上面略有区别。ac代码如下：

class Solution {
        
    	public List<List<Integer>> getSkyline(int[][] buildings) {
        
    		List<int[]> intervals = new ArrayList<>();
    		intervals.add(new int[] {
         0, Integer.MAX_VALUE, 0 });
    		for (int i = 0; i < buildings.length; i++) {
        
    			int[] newb = buildings[i];
    			int j = 0;
    			for (; j < intervals.size() && intervals.get(j)[1] <= newb[0]; ++j) {
        //左闭右开
    			}
    			for (; j < intervals.size() && intervals.get(j)[0] < newb[1]; ++j) {
        //左闭右开
    				int[] inter = intervals.get(j);
    				if (newb[2] > inter[2]) {
        
    					int newL = Math.max(newb[0], inter[0]);
    					int newR = Math.min(newb[1], inter[1]);
    					int oldj = j;
    					if(inter[0]<newL) {
        
    						intervals.add(++j,new int[] {
         inter[0],newL,inter[2] }); 
    					}
    					intervals.add(++j,new int[] {
         newL,newR,newb[2] });  //
    					if(inter[1]>newR) {
        
    						intervals.add(++j,new int[] {
         newR,inter[1],inter[2] }); 
    					}
    					intervals.remove(oldj);
    					--j;
    				}
    			}
    		}
    		
    		List<List<Integer>> ans = new ArrayList<>();
    		for (int i = 0; i < intervals.size(); i++) {
        
    			if(i==0 && intervals.get(i)[2]==0)
    				continue;
    			if(i>0 && intervals.get(i)[2]==intervals.get(i-1)[2])
    				continue;
    			ans.add(Arrays.asList(intervals.get(i)[0],intervals.get(i)[2]));
    			if(i==intervals.size()-1 && intervals.get(i)[2]>0)
    				ans.add(Arrays.asList(intervals.get(i)[1],0));
    		}
    		return ans;
    	}
    }

[LeetCode 57. Insert Interval]: https://leetcode.com/problems/insert-interval/
[Link 1]: https://leetcode-cn.com/problems/insert-interval/solution/cha-ru-qu-jian-by-leetcode-solution/
[20210428111324358.png]: https://img-blog.csdnimg.cn/20210428111324358.png
[3]: https://leetcode-cn.com/problems/insert-interval/solution/shou-hua-tu-jie-57-cha-ru-qu-jian-fen-cheng-3ge-ji/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzMjA0NTU3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210429002006178.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzMjA0NTU3,size_16,color_FFFFFF,t_70
[ac]: https://leetcode.com/submissions/detail/486020079/
[218. The Skyline Problem]: https://leetcode.com/problems/the-skyline-problem/