Java教程

洛谷 P1803题解 java 贪心

本文主要是介绍洛谷 P1803题解 java 贪心,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

现在各大 oj 上有 nn 个比赛,每个比赛的开始、结束的时间点是知道的。

yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。

所以,他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加 22 个及以上的比赛。

输入格式

第一行是一个正数n,接下来n行每行是2个整数ai,bi,表示比赛开始时间,结束时间。

输出格式

一个整数最多参加的比赛数目。

输入输出样例

输入

3
0 2
2 4
1 3

输出

2

做题思路

    相当于就是在数轴上画区间,只要两个区间没有重叠的部分就ok。
    如何判断两个区间没有重复,就是判断前一个区间的末尾有没有小于后一个区间的开始。这样比较关系出来后就需要进行排序,但是是按照开始时间排还是结束时间排,这是一个问题,因为我刚开始想的是按照开始时间排序,很不幸,全wa。
    先来分析下为什么不能能按照开始时间排序,举个例子
    1 10000
    2 1000
    3 100
    4 10

如果按照开始时间进行排序,就是上边的顺序,但是从头开始遍历,判断前一个的结束是否大于等于后一个的开始,如果这样判断,就一场比赛也参加不了。但是如果按照结束时间开始排序,这样就是
    4 10
    3 100
    2 1000
    1 10000
将第一个的结束时间设置为最小的结束时间,从第二个开始判断,如果后面的开始时间大于等于前面的结束时间,就表示这个比赛可以参与,就把后面的结束时间设置为最小的结束时间。
上代码:

 for(int i=1;i<n;i++) {
          if(list.get(i).begin>=minOver) {
              minOver=list.get(i).over;
              cnt++;
          }
        }

接下来就是完整的解题代码

import java.util.*;

public class Main {
    static class Time {
        int begin;
        int over;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        ArrayList<Time> list=new ArrayList<>();
        for(int i=0;i<n;i++) {
            Time time=new Time();
            time.begin=sc.nextInt();
            time.over=sc.nextInt();
            list.add(time);
        }
        int cnt=1;
        list.sort((o1,o2)->o1.over-o2.over);
        int minOver=list.get(0).over;
        for(int i=1;i<n;i++) {
          if(list.get(i).begin>=minOver) {
              minOver=list.get(i).over;
              cnt++;
          }
        }
        System.out.println(cnt);
    }
}

有些人可能疑惑这里sum的初始值为什么是1,因为就算看起来这些时间都有重合,最少都能参加一场比赛

总结

选择不相交区间问题
经典的贪心题
贪心的策略是先给所有的区间按照右边界排序
其中一定要选择第一个区间

这篇关于洛谷 P1803题解 java 贪心的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!