戳气球最少需要几下一样的题

import java.util.*;

public class Main05_1{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int L = sc.nextInt();
        int[][] arr = new int[n][2];
        for(int i=0;i<n;i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        Arrays.sort(arr,(o1,o2)->(o1[0]-o2[0]));

        int res = 0;
        int l = 0, r = 0;
        //l每次都是找最大区间的右边
        for(int[] a:arr){
            //如果当前点在l左边，那么判断他的右边是不是比我定位的r还要大
            if(a[0]<=l){
                r = Math.max(r,a[1]);
            }else{
                //此时在l的右边，且最左边都比我最右边的区间大，那么不连续
                if(a[0]>r){
                    System.out.println(-1);
                    return;
                }
                l = r;
                res++;
                if(r>=L) break;
                r = a[1];
            }
        }
        if(l<r) res++;
        if(r<L) res = -1;
        System.out.println(res);
    }
}

MyCode:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        while (s.hasNext()){
            int n=s.nextInt();
            int L=s.nextInt();
            int[][] arr=new int[n][2];
            for (int i = 0; i < n; i++) {
                arr[i][0]=s.nextInt();
                arr[i][1]=s.nextInt();
            }

            Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));

            int l=0,r=0,res=0;
            for(int[] item:arr){
                if(item[0]<=l){
                    r=Math.max(r,item[1]);//找到可延伸最大的
                    if(r>=L){
                        res++;
                        System.out.println(res);
                        return;
                    }
                }
                else{
                    if(item[0]>r){//最左区间都不在r内，那么不连续
                        System.out.println(-1);
                        return;
                    }
                    res++;
                    l=r;
                    r=item[1];
                    if(r>=L){
                        res++;
                        System.out.println(res);
                        return;
                    }
                }
            }
            if(r<L)  System.out.println(-1);//找到最后最长的区间，长度也不足L
        }
    }
}

LC452戳气球，官方题解：

class Solution {
  public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;

    // sort by x_end
    Arrays.sort(points, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[1] - o2[1];
      }
    });

    int arrows = 1;
    int xStart, xEnd, firstEnd = points[0][1];
    for (int[] p : points) {
      xStart = p[0];
      xEnd = p[1];
      // if the current balloon starts after the end of another one,
      // one needs one more arrow
      if (firstEnd < xStart) {
        arrows++;
        firstEnd = xEnd;
      }
    }

    return arrows;
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/solution/yong-zui-shao-shu-liang-de-jian-yin-bao-qi-qiu-b-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。