The article directories

      • Detonate the balloon with the minimum number of arrows
        • Solution 1: left edge ascending sort, covering from left to right
        • Solution two: left edge ascending sort, covering from right to left
        • Solution three: right edge descending sort, cover from right to left
        • Solution 4: Sort the right boundary in descending order, covering it from left to right
      • 435. No overlap interval
        • Solution 1: right edge ascending order, traversal from left to right
        • Solution 2: left edge ascending order, traversal from right to left

1. The problem of greed is complicated, and Leetcode is a medium starting point; 2, greedy problems are greedy requirements + hard requirements constitute the total requirements of the subject.

Detonate the balloon with the minimum number of arrows

There are many spherical balloons in two dimensions. For each balloon, the input provided is the start and end coordinates of the balloon diameter in the horizontal direction.

Since it’s horizontal, the y-coordinate doesn’t matter, so it’s enough to know where the x-coordinate starts and ends. The start coordinate is always less than the end coordinate.

A bow and arrow can be shot completely vertically from different points along the X-axis. Shoot an arrow at coordinate X. If there is a balloon whose diameter starts and ends at coordinates xstart, xend, and xstart ≤ x ≤ xend, the balloon will be detonated.

There is no limit to the number of bows and arrows that can be fired. Once a bow is fired, it can go indefinitely. We want to find the minimum number of arrows needed to detonate all the balloons.

Give you an array of points, where points [I] = [xstart,xend] returns the minimum number of arrows that must be fired to detonate all the balloons.

Example 1: input: points = [[10,16],[2,8],[1,6],[7,12]]

I’m looking for the intersection of ranges

Explanation: for this example, x = 6 can burst two balloons [2,8],[1,6], and x = 11 can burst the other two balloons

Example 2: inputs: points = [[1,2],[3,4],[5,6],[7,8]] output: 4

Example 3: inputs: points = [[1,2],[2,3],[3,4],[4,5]] output: 2

Example 4: Input: points = [[1,2]] Output: 1

Example 5: input: points = [[2,3],[2,3] output: 1

Local optimal: when the balloons overlap, shoot together with the least bow and arrow. Global optimum: Use the fewest arrows to burst all balloons. Core: is to find the intersection of the scope

Solution 1: left edge ascending sort, covering from left to right

class Solution {
    public int findMinArrowShots(int[][] points) {
      if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] > o2[0]?1: -1;  / / ascending}}); int arrow=1;
      for (int i=1; i<points.length; i++){// select * from [1, length-1]
          if (points[i-1] [1] < points[i][0])
              arrow++;
          else{  Points [i-1][1] >= points[I][0]
              // Point [I][1] points[i-1][1]
              points[i][1] = Math.min(points[i-1] [1],points[i][1]); }}returnarrow; }}Copy the code

Return o1[0]-o2[0]; return o1[0]-o2[0]; Return o1[0] > o2[0]? 1:1;

Else block core: points[I][1] = math.min (points[i-1][1],points[I][1]); 1, because the left boundary has been arranged in ascending order, so i++, each time the left boundary will increase, the right boundary takes the min in the two sections of the current comparison, then the intersection is obtained; 1, I ++, points[i-1][1], else block 1, points[I][1]

Solution two: left edge ascending sort, covering from right to left

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] > o2[0]?1: -1;  / / ascending}}); int arrow=1;
        for (int i=points.length-2; i>=0; i--){// select * from [1, length-1]
            if (points[i][1] < points[i+1] [0])
                arrow++;
            else{ 
                points[i][0] = Math.max(points[i][0],points[i+1] [0]); }}returnarrow; }}Copy the code

The left edge is already in ascending order, so to take Max, just take the one behind it

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                returno1[0] > o2[0] ? 1:1; // ascending}}); int arrow=1;for(int i=points.length-2; i>=0; I --){// select * from [1, length-1]if (points[i][1] < points[i+1][0])
                arrow++;
            else{ points[i][0] = points[i+1][0]; // The left boundary is already sorted, so the assignment is good}}returnarrow; }}Copy the code

Math.max(points[I][0],points[I +1][0]); 1, because the left boundary has been sorted in ascending order, so I -, each time the left boundary will be reduced, the left boundary is the current comparison of the two sections of Max, to obtain the intersection (actually, the left boundary has been sorted, so the direct assignment is good); 1, points[I +1][0] else block 1, points[I][0]

Solution three: right edge descending sort, cover from right to left

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1]?1: -1;  // Sort the right edge in descending order}}); int arrow=1;
        for (int i=1; i<points.length; i++){// select * from [1, length-1]
            if (points[i-1] [0] > points[i][1])  // The left edge of i-1 is larger
                arrow++;
            else{  Points [i-1][1] >= points[I][0]
                // Point [I][1] points[i-1][1]
                points[i][0] = Math.max(points[i-1] [0],points[i][0]); }}returnarrow; }}Copy the code

Else block core: points[I][0] = math. Max (points[I][0],points[I][0]); 1. Since i++ has been arranged in descending order according to the right boundary, the right boundary will be reduced each time, and the left boundary is Max in the two sections of the current comparison, so the intersection is obtained; 1, points[i-1][0] else block 1, points[I][0]

Solution 4: Sort the right boundary in descending order, covering it from left to right

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1]?1: -1;  // The right border is sorted in descending order}}); int arrow=1;
        for (int i=points.length-2; i>=0; i--){// select * from [1, length-1]
            if (points[i+1] [1] < points[i][0])
                arrow++;
            else{  Points [i-1][1] >= points[I][0]
                // Point [I][1] points[i-1][1]
                points[i][1] = Math.min(points[i][1],points[i+1] [1]); }}returnarrow; }}Copy the code

The right edge is already in descending order, so I’m just going to take min and I’m just going to assign it

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                returno1[1] < o2[1] ? 1:1; // right margin descending order}}); int arrow=1;for(int i=points.length-2; i>=0; I --){// select * from [1, length-1]if (points[i+1][1] < points[i][0])
                arrow++;
            else{/ / less than or equal to remove points [I - 1] [1] > = points [I] [0] / / change the element i++, Point [I] [1] is the comparison of above points [I - 1] [1] points [I] [1] = points [I + 1] [1]. }}returnarrow; }}Copy the code

Else block core: points[I][1] = math.min (points[I][1],points[I +1][1]); 1, because the right boundary has been sorted in descending order, so I -, every time the right boundary will increase, the right boundary is the current comparison of the two sections of min, to obtain the intersection (actually, the right boundary has been sorted, so it is good to directly assign); 1, I — points[I +1][1] else block

435. No overlap interval

Given a set of intervals, find the minimum number of intervals that need to be removed (greedy requirement) so that the remaining intervals do not overlap each other (goal).

Note 1: The right boundary is always greater than the left boundary; Note 2: the boundaries of interval [1,2] and [2,3] are “in contact” with each other, not overlapping.

Example 1: input: [[1, 2], [2, 3], [3, 4], [1, 3]] output: 1: after removing [1, 3], the rest of the band didn’t overlap.

Example 2: inputs: [[1,2], [1,2]] output: 2 explanation: you need to remove both [1,2] to make the remaining ranges non-overlapping.

Example 3: input: [[1,2], [2,3]] output: 0 explanation: you do not need to remove any intervals because they are already non-overlapping.

After sorting by right boundary, local optimal: the interval with small right boundary is preferentially selected, so it is traversed from left to right, leaving more space for the next interval, thus avoiding crossover as much as possible. Global optimization: select the most non-crossover intervals (that is, delete the minimum original intervals).

Solution 1: right edge ascending order, traversal from left to right

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length==0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                returno1[1] < o2[1] ? - 1:1; }}); int count=1; // Non-overlapping intervals are initialized to 1 int end=intervals[0][1]; // The first element is boundedfor(int i=1; i<intervals.length; I++){// iterate throughif(life = life, life = life) (life = life, life = life) (life = life, life = life) (life = life, life = life) count++; }}returnintervals.length - count; }}Copy the code

Solution 2: left edge ascending order, traversal from right to left

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length==0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                returno1[0] < o2[0] ? - 1:1; // the left margin is in ascending order, do not use minus sign}}); int count=1; // Non-overlapping intervals are initialized to 1 int start=intervals[enjoy.length-1][0]; // Start with the last element (the element with the largest left margin)for(int i=intervals.length-2; i>=0; I --){// walk throughif(the intervals[I][1] <= start){// The intervals[I][0]; // The intervals[I][0]; count++; }}returnintervals.length - count; }}Copy the code