452. Minimum Number of Arrows to Burst Balloons

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 xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. 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).

这个题需要考虑多种情况才能做


上边儿两种情况都需要两个arrow。
需要知道什么时候new 一个新的arrow：
如果按照start来排序，我们需要新arrow就是当前面的min(end) < cur.start
图一的a.end < c.start
图二的b.end < c.start

 public int findMinArrowShots(int[][] points) {  
     if(points.length == 0) return 0;  
     int n = points.length;  
     Arrays.sort(points, (a, b)->{  
       if(a[0] == b[0]) return Integer.compare(a[1],b[1]);  
       return Integer.compare(a[0],b[0]);  
     });  
     int p1 = 0;  
     int ans = 1;  
     // point 0's end    
     int end = points[0][1];  
     for(int i = 1; i < n; i++){  
       //when end is smaller than next start, we need another arrow  
       //we need to update end, if end is smaller than previous ones  
       end = Math.min(end,points[i][1]);  
       if( end < points[i][0]){  
         end = points[i][1];  
         ans++;  
       }  
     }  
     return ans;  
   }  

435. Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

一开始看题的时候，感觉是backtracking题目。选择overlap的任意一个移除，看结果。但是看了tag之后发现是greedy题目。后来一想，确实是，因为如果两个interval overlap移除end靠后那个就是最优。

需要remove掉overlap的，那么如果a，b overlap，我们就可以移除其中一个。移除的那个我们希望移除那个end 位置靠后的，因为移除那个，可能会减少需要移除的interval

 public class Solution {  
   public int eraseOverlapIntervals(Interval[] intervals) {  
     if(intervals.length == 0) return 0;  
     int n = intervals.length;  
     Arrays.sort(intervals, (a, b)->{  
       if(a.start == b.start) return Integer.compare(a.end, b.end);  
       return Integer.compare(a.start,b.start);  
     });  
     int ans = 0;  
     Interval interval = intervals[0];  
     for(int i = 1; i < n; i++){  
       if(overlap(interval, intervals[i])){  
         ans++;  
         //choose min end  
         if(interval.end > intervals[i].end)  
           interval = intervals[i];  
       }else  
         interval = intervals[i];  
     }  
     return ans;  
   }  
   public boolean overlap(Interval a, Interval b){  
     return (b.start < a.end &&a.start <= b.start)||(a.start < b.end && b.start <= a.start);  
   }  
 }  

376. Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast,[1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

因为是大小大小这样的形式或者小大小大这样

因此，difference will be +-+-+- or -+-+...

所以当不满足条件的时候，就是有连续++ or --出现。那么对于++保存最大位置，对于--保存最小.因此都是记录连续相同符号最开始的差值-------Greedy 

特殊处理，把第一个位置前面想象成和第一个值相同来处理 -> diff 为0。两个连续数字相同的时候不计diff，这样diff 为0只有在k，避免错误。

  public int wiggleMaxLength(int[] nums) {  
     if(nums.length < 2) return nums.length;  
     int ans = 1;  
     int diff = 0;  
     for(int i = 1; i < nums.length; i++){  
       if(nums[i] - nums[i-1] > 0 && diff <= 0){  
         ans++;  
         diff = nums[i] - nums[i-1];  
       }else if(nums[i] - nums[i-1] < 0 && diff >= 0){  
         ans++;  
         diff = nums[i] - nums[i-1];  
       }  
     }  
     return ans;  
   }  

2. dp解法
这道题可以看作是每个位置可以说大的那个位置，也可以是小的那个位置。
因此维护两个dp 一个是形成递增的长度，一个是形成递减的长度
incr[i] = max(incr[i], desc[j]+1)
desc[i] = max(desc[i], incr[j]+1)
O(n^2)

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int size=nums.size();
        if(size==0) return 0;
        vector<int> f(size, 1);
        vector<int> d(size, 1);
        for(int i=1; i<size; ++i){
            for(int j=0; j<i; ++j){
                if(nums[j]<nums[i]){
                    f[i]=max(f[i], d[j]+1);
                }
                else if(nums[j]>nums[i]){
                    d[i]=max(d[i], f[j]+1);
                }
            }
        }
        return max(d.back(), f.back());
    }
};

LongestLineSetWithoutOverlap

给定一组Array 表示每个起始位置和线段长度 {[1,2],[2,5],[3,6],[5,8],[6,10]}  return 不重复的线段最多的条数。例子 return 3

2.

• sort x坐标（两个端点）
• greedy 按终点的位置来计算不重叠
• 从左往右看，如果是左边点就留下。
• 如果是右边点移除这条线，如果这条线和上一条线不重叠，就算上，不然走下一个点

我用了一个pq来做sort以及从左往右扫的功能
用set来存当前位置的所有存在线段
（sweep line 思想，但是比sweep line简单，不用知道是否重叠）
http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/

 public class LongestLineSetWithoutOverlap {  
      static class Line{  
           int left;  
           int right;  
           public Line(int left, int right){  
                this.left= left;  
                this.right = right;  
           }  
           public String toString(){  
                return this.left+", "+this.right;  
           }  
      }  
      static class Point{  
           boolean isLeft;  
           int x;  
           Line line;  
           public Point(int x, boolean isLeft,Line line){  
                this.x = x;  
                this.isLeft = isLeft;  
                this.line = line;  
           }  
      }  
      public static int longestNoOverlap(int[][] nums){  
           PriorityQueue<Point> pq = new PriorityQueue<>((a,b)->(Integer.compare(a.x, b.x)));  
           int max = 0;  
           for(int[] line: nums){  
                Line l = new Line(line[0],line[1]);  
                Point p1 = new Point(line[0],true,l);  
                Point p2 = new Point(line[1],false,l);  
                pq.offer(p1);  
                pq.offer(p2);  
           }  
           Set<Line> T = new HashSet<>();  
           int pre = Integer.MIN_VALUE;  
           while(!pq.isEmpty()){  
                Point p = pq.poll();  
                if(p.isLeft){  
                     T.add(p.line);  
                }else{  
                     //remove line   
                     T.remove(p.line);  
                     if(p.line.left >= pre){  
                          max++;  
                          System.out.println(p.line+" "+pre);  
                          pre = p.x;  
                     }  
                }  
           }  
           return max;  
      }