视野争夺

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int L=in.nextInt();
		int[][] temp=new int[n][2];
		for(int i=0;i<n;i++) {
			for(int j=0;j<2;j++) {
				temp[i][j]=in.nextInt();
			}
		}
		//。获得了数组，进行排序
		Arrays.sort(temp,new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
			}
		});
		int index=0;
		int count=0;
		int pre=0;   //右边界
		while(pre<L) {
			if(temp[index][0]>pre) {
				System.out.println(-1);
			}
			int max=0;
			while(index<n&&temp[index][0]<=pre) {
				max=Math.max(max, temp[index][1]);
				index++;
			}
			count++;
			pre=max;
			if(pre>=L) {
				System.out.println(count);
                return;
			}
			if(index>=n) {
				System.out.println(-1);
                return;
			}
		}
	}
}

//贪心选择
n,L = map(int,input().split())
xy = []
for _ in range(n):
    xy.append(list(map(int,input().split())))
xy.sort(key = lambda x : x[0])
last = 0//当前已选尾部位置
max_reach = 0//当前可选最大到达位置
cnt = 1//ans 先加最后一个
for i in range(n):
    if max_reach >=L:break//一定要加，不然初始化1可能会重复
    if xy[i][0]>max_reach:
        print(-1)
        exit()
    if xy[i][0]>last://此时需要更新last
        last = max_reach//确定选择max_reach
        cnt+=1
        max_reach = max(xy[i][1],max_reach)//勿忘更新max
        continue
    max_reach = max(xy[i][1],max_reach)//日常更新max
if max_reach >= L:
    print(cnt)
else:
    print(-1)

#include <iostream>
#include <map>

using namespace std;

class Solution{
    public:
    void leastCoverdRiver(){
        multimap<int,int> nums;
        int n,L,a,b;
        cin>>n>>L;
        for(int i=0;i<n;i++){
            cin>>a>>b;
            nums.insert(multimap<int,int>::value_type(a,b));
        }
        if(L==0){
            cout<<-1<<endl;
            return;
        }
        int ans=1,l=0,r=nums.begin()->second;;//初始化已经有1个
        for(auto& num:nums){            
                  //判断左边界已经进入下一个阶段,需满足大于之前的边界
            if(l<num.first&&num.second>r){l=r;ans++;}
            if(num.first<=l&&num.second>r){//选出最大的右边界
                r=num.second;
            }
            if(r>=L) break;//满足条件退出
        }
        if(r>=L){//判断是否在该区域内
            cout<<ans<<endl;
        }else{
            cout<<-1<<endl;
        }

    }
};

int main(int argc,char* argv[]){
    Solution().leastCoverdRiver();
    return 0;
}

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int l = scanner.nextInt();
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0])
                return o2[1] - o1[1];
            return o1[0] - o2[0];
        });
        for (int i = 0; i < n; i++) {
            int[] arr = new int[2];
            arr[0] = scanner.nextInt();
            arr[1] = scanner.nextInt();
            queue.offer(arr);
        }
        scanner.close();
        if (queue.peek()[0] != 0) {
            System.out.println(-1);
        } else {
            int from = queue.poll()[1];
            int count = 1;
            PriorityQueue<int[]> queue1 = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
            while (from < l) {
                while (queue.size() > 0 && queue.peek()[0] <= from)
                    queue1.offer(queue.poll());
                if (queue1.size() > 0 && queue1.peek()[1] > from) {
                    from = queue1.poll()[1];
                    count++;
                } else {
                    System.out.println(-1);
                    return;
                }
            }
            System.out.println(count);
        }
    }
}

import java.util.*;
public class Main{
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int l = in.nextInt();
        int[][] guard = new int[n][2];
        for (int i = 0;i < guard.length; ++i) {
            guard[i][0] = in.nextInt();
            guard[i][1] = in.nextInt();
        }
        Arrays.sort(guard, (a, b) -> a[0]-b[0]);
        if (guard[0][0] > 0) System.out.println(-1);
        int end = guard[0][1];
        int cnt = 1;
        int max = end;
        for (int i = 1;i < guard.length; ++i) {
            if (guard[i][0] <= end) {
                max = Math.max(max, guard[i][1]);
            } else {
                if (guard[i][0] > max)
                    System.out.println(-1);
                else {
                    end = max;
                    max = guard[i][1];
                    cnt++;
                }
            }
            if (end >= l) {
                System.out.println(cnt);
                return;
            }
        }
        if (end != max){
            end = max;
            cnt++;
        }
        if (end >= l) {
            System.out.println(cnt);
        } else {
            System.out.println(-1);
        }
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int L = in.nextInt();
        int[][] arr = new int[n][2];
        for(int i =0;i<n;i++){
            for(int j =0;j<2;j++){
                arr[i][j] = in.nextInt();
            }
        }
        
        //贪心思想，每次找右边值能覆盖最大范围，所用个数最小
        
        //按左边值排序
        Arrays.sort(arr, (int[] o1,int[] o2)-> o1[0]-o2[0]);

       int rowIndex = 1;
        
        int count = 1;
        //第一个值存起来，后面的遍历与这个比较
        int[] temp = arr[0];
        //保存右边值得最大值，
        int maxValue = temp[1];
        //如果开头不为0则返回-1
        if (temp[0] != 0){
            System.out.println(-1);
            return;
        }
        while(rowIndex<arr.length){
          //如果右边最大值超过L则说明覆盖完全，++count是因为要加上maxValue这个守卫
            if(maxValue >=L){
                System.out.println(++count);
                return;
            }
            //最开始的右边值覆盖不住左边值时，说明要换守卫，所以守卫加一，并更新右边值
            if(arr[rowIndex][0] > temp[1]){
                count++;
                temp[1] = maxValue;
            }else{
                maxValue = Math.max(maxValue,arr[rowIndex][1]);
                rowIndex++;
            }
        }
        //如果符合条件的在最后一个，则maxValue此时就是能够覆盖的值，所以需要再进行判断
        if(maxValue >=L){
            System.out.print(++count);
        }else{
            //如果都没有符合条件的值，同样会遍历完
            System.out.print(-1);
            
        }
        
        
    }
}

package main

import "fmt"
import "sort"

func covered(nums [][]int, length int) int {
	sort.Slice(nums,func(i, j int) bool {
		if nums[i][0] == nums[j][0] {
			return nums[i][1] > nums[j][1]
		} else {
			return nums[i][0] < nums[j][0]
		}
	})
	pre_end := 0
	start := 0
	res := 0 
    for start < len(nums) {
        if nums[start][0] > pre_end {
            return -1
        }
        k := start + 1
        max := nums[start][1]
        for k < len(nums) && nums[k][0] <= pre_end {
            if max < nums[k][1] {
                max = nums[k][1]
            }
            k++
        }
        pre_end = max
        res++
        start = k
        if pre_end >= length {
            break
        }        
    }
    if pre_end < length {
        return -1
    }
	return res
}

func main() {
	var n, l int
	fmt.Scanln(&n,&l)
	var a,b int
	nums := [][]int{}
	for i := 0; i < n; i++ {
		fmt.Scanln(&a,&b)
		nums = append(nums, []int{a,b})
	}
	ans := covered(nums,l)
	fmt.Println(ans)
}
无论如何都只过60%是怎么回事啊？求大佬带教教我

该题关键是要完全覆盖河道.

我们可以将覆盖区间的起始点从小到大排序, 若起始点相同,那么在根据结束点排序.

我们只需从左往右看, 在目前能到达的长度下, 尽可能挑选一个照的远的眼. 当眼的起始点已经超过目前能到达的长度时

• 眼数 + 1

• 目前能到达的长度 = 尽可能挑选一个照的远的眼的长度
      

  #include <algorithm>
  #include <iostream>
  #include <stack>
  #include <vector>
  using namespace std;
  
  
  class Solution {
  public:
  };
  
  struct Comparator {
    // 我们可以将覆盖区间的起始点从小到大排序, 若起始点相同,那么在根据结束点排序.
      bool operator()(pair<int, int> p1, pair<int, int> p2) {
          if (p1.first == p2.first)
              return p1.second < p2.second;
          else
              return p1.first < p2.first;
      }
  } comparator;
  
  int main() {
      int n, l;
      cin >> n >> l;
      pair<int, int> sections[100000];
      for (int i = 0; i < n; ++i) {
          cin >> sections[i].first >> sections[i].second;
      }
    	// 排序
      sort(sections, sections + n, comparator);
      int i = 0;
      int newLength = 0;
      // 去除被完全覆盖的区间 如 [0, 9], [0, 8]其中[0, 8]是不可能选择的, 要尽可能少买眼, 所以只用考虑照亮区间大的
      while (i < n) {
          int val = sections[i].first;
          while (val == sections[i].first) {
              ++i;
          }
          sections[newLength++] = sections[i - 1];
      }
    	// 若连最开始的眼都找不了开头, 那不可能完全覆盖
      if (sections[0].first > 0) {
          cout << "-1";
          return 0;
      }
    	// 更新区间数组长度
      n = newLength;
      i = 0;
    	// 要买的眼数
      int output = 0;
      // 未来可以到达的长度
      int tail = sections[0].second;
      // 目前可以到达的长度
      int last = -1;
      while (i < n) {
  				// 在可以到达的长度时, 尽可能选择能照更远的
          while (i < n && sections[i].first <= last) {
              tail = max(tail, sections[i].second);
              ++i;
          }
        	// 目前sections[i] 已经超过目前可以到达的长度, 逼不得已买一个眼, 这个眼就是之前`尽可能选择能照更远的`的眼
          ++output;
          last = tail;
        	// 若目前能到达的长度已经超过l, 可以完全覆盖
          if (last > l) {
              cout << output;
              return 0;
          }
        	// 不连续, 不能完全覆盖
          if (sections[i].first > tail) {
              cout << "-1";
              return 0;
          }
      }
    	// 区间用完了, 但若目前能到达的长度也到达不了l
      if (tail < l)
          cout << "-1";
  }

  
  
  

#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;


int main(){
    int n, L;
    cin >> n >> L;
    vector<vector<int>> spans(n,vector<int>(2,0));
    for(int i =0; i < n; i++){
        cin >> spans[i][0] >> spans[i][1];
    }
    sort(spans.begin(), spans.end());
    int ans = 0;
    // 贪心算法
    int l = 0, r = 0;
    int left = 0, right = n - 1;
    // bool ok = false;
    while(left <= right){
        int i = left;
        while(i <= right && spans[i][0] <= l && r < L){
            r = max(r, spans[i][1]);
            i ++;
        }
        l = r;
        if(r >= L){
            cout << ans + 1<< endl;
            return 0;
        }
        if(left == i){
           cout << -1 << endl;
           return 0;
        }
        ans ++;
        left = i;
    }
    cout << -1 << endl;
    return 0;
 
}

package main

import (
    "fmt"
    "sort"
    "bufio"
    "strings"
    "strconv"
    "os"
)

type pair struct{
    a,b int
}
func main(){
    var n,l int
    fmt.Scan(&n,&l)
    inp:=bufio.NewReader(os.Stdin)
    li:=make([]pair,n)
    for i:=0;i<n;i++{
        str,_:=inp.ReadString('\n')
        str_l:=strings.Split(str[:len(str)-1]," ")
        li[i].a,_=strconv.Atoi(str_l[0])
        li[i].b,_=strconv.Atoi(str_l[1])
    }
    sort.Slice(li,func(i,j int)bool{
        if li[i].a!=li[j].a{
            return li[i].a<li[j].a
        }else{
            return li[i].b>li[j].b
        }
    })
    r:=0
    con:=0
    id:=0
    for r<l{
        if li[id].a>r{
            fmt.Println(-1)
            return
        }
        p:=0
        for ;id<n&&li[id].a<=r;id++{
            p=max(p,li[id].b)
        }
        r=p
        con++
        if r>=l{
            fmt.Println(con)
            return 
        }
        if id>=n{
            fmt.Println(-1)
            return
        }
    }
}
func max(a,b int)int{
    if a>b{
        return a 
    }
    return b
}

n, L = [int(x) for x in input().split()]
nums = []
while(n>0):
    n -= 1
    tmp = [int(x) for  x in input().split()]
    nums.append(tmp)

nums.sort(key=lambda x: (x[0], -1*x[1]))
pre_end = nums[0][1]
ans = [nums[0]]
cover_max = 0
i = 1
while i < len(nums):
    start, end = nums[i][0], nums[i][1]
    if start <= pre_end:
        cover_tmp = end - pre_end
        if cover_max < cover_tmp:
            i_select = i
            cover_max = cover_tmp
        i += 1
    else:
        ans.append(nums[i_select])
        pre_end = nums[i_select][1]
        cover_max = 0
        if pre_end >= L:
            break
if pre_end < L:
    ans.append(nums[i_select])

if ans[-1][1]>= L:
    print(len(ans))
else:
    print(-1)