[Java知识库]JAVA(OJ1009)

1009: 1-2-1 Milking Cows 挤牛奶

题目：

输入格式
一个整数N。
每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。
输出格式
一行，两个整数，即题目所要求的两个答案。
样例输入

3
300 1000
700 1200
1500 2100

样例输出

900 300

思路：
贪心，先对区间通过左端点排序，然后从左到右遍历每段区间。若左端点在上一区间内部，则更新右端点r；否则，更新答案res1，res2，然后更新l，r。最后不要漏掉最后一段区间对res1的作用。
代码：

import java.util.*;

public class Main{
    public static int N = 5010;
    public static int n;
    public static int a, b;
    public static Map<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for(int i = 0; i < n; i ++ ){
            a = scanner.nextInt();b = scanner.nextInt();
            map.put(a, b);
        }
        // 对map的key进行排序(左端点)
        List<Map.Entry<Integer,Integer>> listOfMap = new ArrayList<Map.Entry<Integer,Integer>>(map.entrySet());// 取出集合再化为列表
        Collections.sort(listOfMap, new Comparator<Map.Entry<Integer,Integer>>() {
            //升序排序
            public int compare(Map.Entry<Integer, Integer> o1,
                               Map.Entry<Integer, Integer> o2) {
                return o1.getKey().compareTo(o2.getKey());
            }

        });
//        System.out.println(listOfMap);
        Map.Entry<Integer,Integer> first = listOfMap.stream().findFirst().orElse( null );
//        System.out.println(first);
        // 贪心
        int res1 = 0, res2 = 0;
        int l = first.getKey(), r = first.getValue();
        for(Map.Entry<Integer,Integer> item:listOfMap){
            if(item.getKey() <= r) r = Math.max(r, item.getValue());
            else{
                res1 = Math.max(res1, r - l);
                res2 = Math.max(res2, item.getKey() - r);
                l = item.getKey();
                r = item.getValue();
            }
        }
        res1 = Math.max(res1, r - l); // 最后一段别漏了
        System.out.println(res1 + " " + res2);
    }
}

效果图：