leetcode 452. Minimum Number of Arrows to Burst Balloons | 452. 用最少数量的箭引爆气球（左程云：最大线段重合问题）

绝地灬酷狼 2022-09-06 00:16 139阅读 0赞

## 题目 ##

[https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/][https_leetcode.com_problems_minimum-number-of-arrows-to-burst-balloons]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

重叠区间问题可以总结为在坐标轴上若干个位置为 (start(i),end(i)) 的区间，要求求解这些区间中有多少个不重叠区间，或者合并重叠的区间。

对于重叠区间问题，海外版评论区有人总结了模板，见 [A Concise Template for “Overlapping Interval Problem”][A Concise Template for _Overlapping Interval Problem]

该问题分两类：第一类求重叠区间个数（leetcode 452，435），第二类求合并后的区间（leetcode 56，763）。  
对于第一类问题，通常按照end排序，维护一个end变量即可。  
对于第二类问题，通常按照start排序，维护一个数组，每次取最后一个数作为比较的标准。  
注意按照 start 或者 end 排序两种方式都可以求解，只是在不同情况下用其中之一代码编写更简洁。

本文总结了leetcode中重叠区间问题的题目，涉及到的题目如下：

*  leetcode 56 合并区间
 *  leetcode 452 射气球
 *  leetcode 435 无重叠区间
 *  leetcode 763 划分字母区间

##### 本题思路 #####

回到本题，思路是，维护一个小根堆，里面存 end，当 start 大于最小的 end 时，说明前面的线段和当前的线段不可能同时被切，所以把前面的线段全部一刀切。

后来发现，不需要维护小根堆，只要用一个变量维护最小值就可以了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public int findMinArrowShots(int[][] points) { 
            Arrays.sort(points, (o1, o2) -> (long) o1[0] - (long) o2[0] > 0 ? 1 : -1);
            int count = 0;
            long minEnd = Long.MAX_VALUE;
            for (int[] pair : points) { 
                if (minEnd != Long.MAX_VALUE && pair[0] > minEnd) { 
                    minEnd = Long.MAX_VALUE;
                    count++;
                }
                minEnd = Math.min(minEnd, pair[1]);
            }
            return count + 1; // 清算结尾
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

## 思路来源：左程云“最大线段重合问题” ##

另外，对于“[求重叠最多的绳子条数][Link 1]”问题，见视频 15:49  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

package class04_07;
    
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class Code01_CoverMax { 
    
    	public static int maxCover1(int[][] lines) { 
    		int min = Integer.MAX_VALUE;
    		int max = Integer.MIN_VALUE;
    		for (int i = 0; i < lines.length; i++) { 
    			min = Math.min(min, lines[i][0]);
    			max = Math.max(max, lines[i][1]);
    		}
    		int cover = 0;
    		for (double p = min + 0.5; p < max; p += 1) { 
    			int cur = 0;
    			for (int i = 0; i < lines.length; i++) { 
    				if (lines[i][0] < p && lines[i][1] > p) { 
    					cur++;
    				}
    			}
    			cover = Math.max(cover, cur);
    		}
    		return cover;
    	}
    
    	public static int maxCover2(int[][] m) { 
    		Line[] lines = new Line[m.length];
    		for (int i = 0; i < m.length; i++) { 
    			lines[i] = new Line(m[i][0], m[i][1]);
    		}
    		Arrays.sort(lines, new StartComparator());
    		// 小根堆，每一条线段的结尾数值，使用默认的
    		PriorityQueue<Integer> heap = new PriorityQueue<>();
    		int max = 0;
    		for (int i = 0; i < lines.length; i++) { 
    			// lines[i] -> cur 在黑盒中，把<=cur.start 东西都弹出
    			while (!heap.isEmpty() && heap.peek() <= lines[i].start) { 
    				heap.poll();
    			}
    			heap.add(lines[i].end);
    			max = Math.max(max, heap.size());
    		}
    		return max;
    	}
    
    	public static class Line { 
    		public int start;
    		public int end;
    
    		public Line(int s, int e) { 
    			start = s;
    			end = e;
    		}
    	}
    
    	public static class EndComparator implements Comparator<Line> { 
    
    		@Override
    		public int compare(Line o1, Line o2) { 
    			return o1.end - o2.end;
    		}
    
    	}
    
    	// for test
    	public static int[][] generateLines(int N, int L, int R) { 
    		int size = (int) (Math.random() * N) + 1;
    		int[][] ans = new int[size][2];
    		for (int i = 0; i < size; i++) { 
    			int a = L + (int) (Math.random() * (R - L + 1));
    			int b = L + (int) (Math.random() * (R - L + 1));
    			if (a == b) { 
    				b = a + 1;
    			}
    			ans[i][0] = Math.min(a, b);
    			ans[i][1] = Math.max(a, b);
    		}
    		return ans;
    	}
    
    	public static class StartComparator implements Comparator<Line> { 
    
    		@Override
    		public int compare(Line o1, Line o2) { 
    			return o1.start - o2.start;
    		}
    
    	}
    
    	public static void main(String[] args) { 
    
    		Line l1 = new Line(4, 9);
    		Line l2 = new Line(1, 4);
    		Line l3 = new Line(7, 15);
    		Line l4 = new Line(2, 4);
    		Line l5 = new Line(4, 6);
    		Line l6 = new Line(3, 7);
    
    		// 底层堆结构，heap
    		PriorityQueue<Line> heap = new PriorityQueue<>(new StartComparator());
    		heap.add(l1);
    		heap.add(l2);
    		heap.add(l3);
    		heap.add(l4);
    		heap.add(l5);
    		heap.add(l6);
    
    		while (!heap.isEmpty()) { 
    			Line cur = heap.poll();
    			System.out.println(cur.start + "," + cur.end);
    		}
    
    		System.out.println("test begin");
    		int N = 100;
    		int L = 0;
    		int R = 200;
    		int testTimes = 200000;
    		for (int i = 0; i < testTimes; i++) { 
    			int[][] lines = generateLines(N, L, R);
    			int ans1 = maxCover1(lines);
    			int ans2 = maxCover2(lines);
    			if (ans1 != ans2) { 
    				System.out.println("Oops!");
    			}
    		}
    		System.out.println("test end");
    	}
    }

[https_leetcode.com_problems_minimum-number-of-arrows-to-burst-balloons]: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/549fddbb0ca1458f86645d9fb94fd955.png
[A Concise Template for _Overlapping Interval Problem]: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/discuss/93735/A-Concise-Template-for-%22Overlapping-Interval-Problem%22
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/8791bde4921c4c6f841963f9d3620fa3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/d051f40f885349289d7f566a06b25cd2.png
[Link 1]: https://ke.qq.com/webcourse/3067253/103187834#taid=10471980674239861&vid=5285890810611674308
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/713681fa21a246a79b95f99c0d2cc8c1.png