MinimumNumberOfArrowsToBurstBalloons [source code]
public class MinimumNumberOfArrowsToBurstBalloons {
static
/******************************************************************************/
class Solution {
public int findMinArrowShots(int[][] points) {
if (points == null || points.length == 0 || points[0].length == 0)
return 0;
Arrays.sort(points, (a,b) -> (a[0] - b[0]));
int end = points[0][1], count = 1;
for (int i = 1; i < points.length; i++) {
if (points[i][0] > end) {
end = points[i][1];
count++;
} else {
end = Math.min(end, points[i][1]);
}
}
return count;
}
}
/******************************************************************************/
public static void main(String[] args) {
MinimumNumberOfArrowsToBurstBalloons.Solution tester = new MinimumNumberOfArrowsToBurstBalloons.Solution();
}
}
这个题目的题意还是很好理解的, 然后当然就是开始想一个人逻辑, 但是这个人逻辑却不是那么好想; 看起来其实很简单的一个任务, 就是合理的安排一下overlapping的问题, 最后却连一个基本的笨办法都想不出来; 目前其实还是没有思路的, 不过这种时候我还是提出一个主张, 就是简单升级: 如果你想到了一个哪怕看起来非常蠢的笨办法, 也不要太快否决, 尽量丰实一下, 然后看看能不能借助于这个算法来达到对题目更深刻的理解, 找到更好的优化方案;
想到一个做法, 就是一旦两个interval有overlapping, 就用overlapping这个小的interval来代替原来的两个, 也就是这两个大的就不存在了; 这个算法看上去应该是对的, 但是有一个小的疑问, 这里这个类似于改造的过程, 用什么顺序来进行呢? 比如题目给的这个例子:
1 6 //1
2 8 //2
7 12 //3
10 16 //4
这个如果我们1,2合并, 然后3,4合并, 最后是可以得到争取的结果, 最后只剩下两个不相交的interval; 但是如果我们先把2,3合并, 最后得到的就是3, 就是不对的结果;
另外这个题目是一个明显的最值搜索问题, 这里想到用确定搜索还是挺正常的, 不过tag里面的这个greedy我还是有点不理解;
时间到了没有想出很好的解法, 放弃了这一题;
上面代码是模仿最优解写的一个, 虽然现在确实也不是彻底理解了这个问题; 速度是125ms (11%), 不知道为什么这么慢; 把几个最优解试了一下, 好像是这个lambda的原因; 以前知道用java8的stream很慢, 没想到lambda也这么慢;
public int findMinArrowShots(int[][] points) {
if(points==null || points.length==0 || points[0].length==0) return 0;
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if(a[0]==b[0]) return a[1]-b[1];
else return a[0]-b[0];
}
});
int minArrows = 1;
int arrowLimit = points[0][1];
for(int i=1;i<points.length;i++) {
int[] baloon = points[i];
if(baloon[0]<=arrowLimit) {
arrowLimit=Math.min(arrowLimit, baloon[1]);
} else {
minArrows++;
arrowLimit=baloon[1];
}
}
return minArrows;
}
这个是discussion最优解, 思路还是非常简单的, 直接就从左到右取做(我一开始也是想要采用这个ordering的); 但是他这里的核心思路跟我上面的算法是不一样的, 他这里的做法的核心其实是, 就从第一个balloon出发, 在这个balloon的interval内的每一个点, 我们其实都可以安排这个arrow(我们最终的目标是一定要把所有的interval都射掉, 所以第一个interval一定至少有一根arrow穿过); 我们尽可能的往右(greedy)安排这个arrow, 这样我们同时可以射掉第二个interval的机会就最大(记得greedy到底是怎么做的吗? 我们只站在当前的位置/iteration根据一个最值的策略取选择这一步的动作, 我们用到的信息顶多是我们的下一个邻居, 而不可能是全局或者更远的历史信息);
如果我们在保证第一个interval能够被射掉的情况下, 还是无法保证射掉第二个interval, 那么只能说第一个arrow能做到的只有这么多了, 这个时候就只能类似于一个刷新的观点, 给第二个interval一个新的arrow, 相当于刷新了一下起点;
其实这个问题自己在想算法的情况下, 还是很多情况需要考虑的, 比如如果三个interval有一个共同的overlapping怎么办? 这种情况就跟我们上面的例子那里, 三个interval只有两两想接的情况的处理方式不一样; 但是这里这个greedy算法最后厉害的地方, 就是可以无视这个差别, 无视这个枚举的需求, 直接一个策略就可以照顾到所有的情形;
另外, 我自己的想法的时候, 我画的图也比较奇怪, 不是我这里上面这个抽屉一样的图, 而是一个类似数轴上的区间的图, 虽然最后overlapping看的比较清晰, 但是这样的visual相对就不太容易诱导出这里这个greedy的思路;
不过还是要注意一下的是这里sort的顺序, 先根据起点sort, 然后根据终点, 说明这个作者背后还是有丰富的思考的; 虽然我自己最终没有写出来一个解法, 但是这个情况我在自己思考的时候就没有去考虑过;
另外, interval问题好像这种sort是不是已经成为常规了都?
但是有人提出, 这个算法其实还可以进一步简化:
public int findMinArrowShots(int[][] points) {
if(points==null || points.length==0) return 0;
// sort points based on their end point.
Arrays.sort(points, new Comparator<int[]>(){
public int compare(int[] p1, int[] p2)
{
return Integer.compare(p1[1],p2[1]);
}
});
int currentEnd = points[0][1];
int count = 1;
for(int[] p: points)
{
// if the point starts after currentEnd, it means this balloons not been bursted. Then we shot the balloon in its end point. Otherwise, means this balloon has been bursted, then ignore it.
if(p[0]>currentEnd) {
count++;
currentEnd = p[1];
}
else continue;
}
return count;
}
为什么我们这里只要sort end就可以了? 当我们做一个从左到右的扫描的时候, 我们其实可以理解为有一个射击难度的概念, 也就是the difficulty of shooting the balloon with an arrow at the left; 我们这里greedy的过程, 其实就是从左到右, 比如第一个interval, 我们保证能够射掉, 然后我们继续向右探索, 看看有没有其他的interval可以被同一个arrow给射掉; 一个interval的end越靠右, 那么射击它的难度就越大; 至于start, 其实是无需比较的, 在射击的过程中进行一个比较判断就行了, 不需要单独进行sort;
好像还是没有细致的解决这个问题本质上的悬念;
这里是一个人尝试解释这个算法的正确性:
@flando said in Java Greedy Soution:
@wsliubw From an easy to understand point of view, this greedy algorithm works because : 1, when sorted by end value, you will always need a shot for the first balloon(at its end) because if it's a stand alone balloon you obviously have to otherwise it has other balloons overlapping, in which case you also have to use an arrow at its end otherwise you will miss this balloon. 2, If you have overlapping balloon, it's good, your arrow will destroy them, and this way, you are creating a sub-problem, which start with a new set of balloons with these characteristics. You keep doing until no balloon is left.
这个人的解释其实还是比较naive的, 而且并没有给出一个很系统的证明, 但是他这里这个subproblem的概念的使用还是值得学习的; greedy在一定意义上就是一个特殊的DP, 所以在greedy问题当中其实也是有subproblem这个概念和DP structure的, 只不过大部分时候不这么想, 很多时候直接就把greedy当成一个直白的确定搜索了; 但是有时候, 适当的去从DP的角度(reduce the problem)取思考一下greedy未必不是一件好事;
另外一个解法:
@zzhai said in Java Greedy Soution:
Typical greed algorithm. The question is equivalent to ask - maximally, how many non-overlapping balloons we can find? Each non-overlapping balloon will take 1 arrow to burst.
Similar problems -
public int findMinArrowShots(int[][] points) {
int n = points.length;
if (n <= 1) return n;
PriorityQueue<int[]> pq = new PriorityQueue<>((p1, p2) -> p1[1] - p2[1]);
for (int i = 0; i < n; i++)
pq.offer(points[i]);
int cnt = 1, end = pq.poll()[1];
for (int i = 1; i < n; i++) {
int[] cur = pq.poll();
if (cur[0] > end) {
cnt++;
end = cur[1];
}
}
return cnt;
}
这个人第一句的解释还是挺好的; 我看到这个题目的时候也感觉这个题目背后应该有一个很general的需求还是什么东西, 但是没有想到; 这里他就想到了, 这个问题最后事实上类似于找到有多少个孤岛, 或者有点像找CC的问题?
算法本身其实跟上面那个算法是一样的, 直接sort end就行了;
底下有一个人质疑他的观点, 不过最后反而看起来好像是证明了他的观点:
@wxl163530 said in Java Greedy Soution:
@zzhai Hello, I am a little confused about the equivalent saying" how many non-overlapping balloons we can find". In this case, even we get the maximal non-overlapping balloons, we still need some extra arrows. Eg.
|---------b1---||----b2---------||-----b3---||------b4-----|
|-b5--||--b6-| |--b7-||-b8-|
so that we need 6 arrows rather than 4
b1 to b8 are the ballons
之所以只要找到maximal non-overlapping的就行了...这个证明好像还挺难的? 我可以先claim, 假如我们找到了一个set of maximal non-overlapping intervals, 那么只要我们给每一个interval一个arrow, 最后肯定可以射掉所有的balloon, 包括这个set里面的这些balloon, 以及any balloon that overlaps with any of the balloons in the set; 首先, 证明set里面的这些个可以被射掉是很简单的; 难的是, 给每一个"代表"一箭, 能够保证所有和他有overlapping的吗? 假如有这样的情况:
[ ] [ ]
[ ] //rep
上面是两个被代表的, 这种情况下, 确实一箭是解决不掉的, 注意, 这两个被代表的interval跟任何其他的代表是不overlap的(如果有overlap的话讨论就复杂很多了, 感觉要用induction来做了); 那么这个情况下, 我们用下面的这个做代表, 是不如用上面的这两个来做代表的, 也就是说这种情况contradicts with the statement of MAXIMAL;
假如两个被代表的interval还跟其他的代表有overlapping, 好像证明起来是复杂一些, 稍微画了一下, 可能性太多了; 像这种可能性太多的情况, 是不是可以从更加宏观的上帝视角找到一个方法呢? 首先这个set里面的代表全都是disjoint的, 然后我们假设有一个interval X, 不是代表, 那么它就至少跟一个代表overlap; 然后我们假设每个代表只给一箭的情况下, 这个X无法被射掉; 还是想不到怎么证明, 最接近的是一个思路是考虑对于每一个代表, 它的所有的affiliate在这个代表身上留下的投影; 不过这个角度最终还是没有找到能够真正证明的思路;
另一个帖子:
@Joshua924 said in Share my explained Greedy solution as the highest voted java solution right now is not ideal:
No offense but the currently highest voted java solution is not ideal, the sorting can be adjusted so that there's no need to check again in the for loop.
Idea:
We know that eventually we have to shoot down every balloon, so for each ballon there must be an arrow whose position is between balloon[0] and balloon[1]. Given that, we can sort the array of balloons by their ending position. Then we make sure that while we take care of each balloon from the beginning, we can shoot as many following balloons as possible.So what position should we pick? We should shoot as right as possible, because all balloons' end position is to the right of the current one. Therefore the position should be currentBalloon[1], because we still need to shoot down the current one.
This is exactly what I do in the for loop: check how many balloons I can shoot down with one shot aiming at the ending position of the current balloon. Then I skip all these balloons and start again from the next one (or the leftmost remaining one) that needs another arrow.
Example:
balloons = [[7,10], [1,5], [3,6], [2,4], [1,4]]After sorting, it becomes:
balloons = [[2,4], [1,4], [1,5], [3,6], [7,10]]So first of all, we shoot at position 4, we go through the array and see that all first 4 balloons can be taken care of by this single shot. Then we need another shot for one last balloon. So the result should be 2.
Code:
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
Arrays.sort(points, (a, b) -> a[1] - b[1]);
int arrowPos = points[0][1];
int arrowCnt = 1;
for (int i = 1; i < points.length; i++) {
if (arrowPos >= points[i][0]) {
continue;
}
arrowCnt++;
arrowPos = points[i][1];
}
return arrowCnt;
}
他上开始说的那个not ideal的解法我也没有看到, 不过大概猜测一下, 应该还是遵循这一球一箭的总原则, 先给每一个balloon一箭, 然后移动这一箭的位置; 使得这一箭可以射到更多的其他的球; 如果没有sort的话, 那么只能先射一个球, 然后过一遍找到所有overlap的, 射掉其他的overlap的, 并且更新remaining pool? 不知道到底是什么意思? 具体的代码不知道怎么写的;
另外注意一个小问题, 虽然我们这里的做法是一个一球一箭的做法, 不代表最终每一个interval最多只有一箭, 就比如上面那个:
[ ] [ ]
[ ] //rep
这里, 下面这个代表最后就肯定要吃两箭;
然后可以大概看一看他这里的讲解, 其实也不是非常的细腻, 基本还是一个意识流的讲解;
这个是最开始discussion1的简化写法:
public class Solution {
public int findMinArrowShots(int[][] points) {
if(points == null || points.length < 1) return 0;
Arrays.sort(points, (a, b)->(a[0]-b[0]));
int result = 1;
int end = points[0][1];
for(int i = 1; i < points.length; i ++) {
if(points[i][0] > end) {
result ++;
end = points[i][1];
} else {
end = Math.min(end, points[i][1]);
}
}
return result;
}
}
所以这个题目最后其实就是分别的两种写法, 一个是sort start, 一个是sort end;
sort start这个做法的这个min操作, 如果自己写的话, 感觉相对来说不是那么容易想出来;
这个是一个不错的总结:
@wangxinbo said in A Concise Template for "Overlapping Interval Problem":
Here I provide a concise template that I summarize for the so-called "Overlapping Interval Problem", e.g. Minimum Number of Arrows to Burst Balloons, and Non-overlapping Intervals etc. I found these problems share some similarities on their solutions.
- Sort intervals/pairs in increasing order of the start position.
- Scan the sorted intervals, and maintain an "active set" for overlapping intervals. At most times, we do not need to use an explicit set to store them. Instead, we just need to maintain several key parameters, e.g. the number of overlapping intervals (count), the minimum ending point among all overlapping intervals (minEnd).
- If the interval that we are currently checking overlaps with the active set, which can be characterized by cur.start > minEnd, we need to renew those key parameters or change some states.
- If the current interval does not overlap with the active set, we just drop current active set, record some parameters, and create a new active set that contains the current interval.
int count = 0; // Global parameters that are useful for results.
int minEnd = INT_MAX; // Key parameters characterizing the "active set" for overlapping intervals, e.g. the minimum ending point among all overlapping intervals.
sort(points.begin(), points.end()); // Sorting the intervals/pairs in ascending order of its starting point
for each interval {
if(interval.start > minEnd) { // If the
// changing some states, record some information, and start a new active set.
count++;
minEnd = p.second;
}
else {
// renew key parameters of the active set
minEnd = min(minEnd, p.second);
}
}
return the result recorded in or calculated from the global information;
For example, for the problem Minimum "Number of Arrows to Burst Balloons", we have
- Sort balloons in increasing order of the start position.
- Scan the sorted pairs, and maintain a pointer for the minimum end position for current "active balloons", whose diameters are overlapping.
- When the next balloon starts after all active balloons, shoot an arrow to burst all active balloons, and start to record next active balloons.
int findMinArrowShots(vector<pair<int, int>>& points) {
int count = 0, minEnd = INT_MAX;
sort(points.begin(), points.end());
for(auto& p: points) {
if(p.first > minEnd) {count++; minEnd = p.second;}
else minEnd = min(minEnd, p.second);
}
return count + !points.empty();
}
For the problem "Non-overlapping Intervals", we have
int eraseOverlapIntervals(vector<Interval>& intervals) {
int total = 0, minEnd = INT_MIN, overNb = 1;
sort(intervals.begin(), intervals.end(), [&](Interval& inter1, Interval& inter2) {return inter1.start < inter2.start;});
for(auto& p: intervals) {
if(p.start >= minEnd) {
total += overNb-1;
overNb = 1;
minEnd = p.end;
}
else {
overNb++;
minEnd = min(minEnd, p.end);
}
}
return total + overNb-1;
}
这个总结的模板还是挺有意思的; 而且这个active set的概念很有意思, 想想好像还是这么一回事; 当然, 这个active set的概念最后是可以归类到历史信息流算法的类别里面的, 只不过是这里的这个历史信息结构, 有点特殊;
所以其实sort start是更加general的做法? 这个还是有点没有想到; 另外, 他这的minEnd的处理并不是最理想的思路, 不过还是可以学习一下;
另外, 这个min操作, 感觉在Non-overlapping Intervals这个题目的设定下, 好像更难想到一些;
暂时就看到这么多解法了, 反正最后就归类到两个sort的解法; 另外, 有一个提到的not ideal的解法到现在都没有看到, 有点慌;
另外, 看了不少帖子, 感觉并没有人真正对这个问题提出足够深刻的理解, 这里的这个greedy到底是什么样的一个思考方式的指导下想出来的, 这些都没有;
Problem Description
There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_end bursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
Example:
Input:
[[10,16], [2,8], [1,6], [7,12]]
Output:
2
Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
Difficulty:Medium
Total Accepted:14.5K
Total Submissions:32.9K
Contributor: Leets4Eternity
Companies
microsoft
Related Topics
greedy
Similar Questions
Meeting Rooms II Non-overlapping Intervals