奶牛过马路

题目

链接：1978. 奶牛过马路 - AcWing题库

每天，农夫约翰的 N 头奶牛都会穿过农场中间的马路。

考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0 描述，另一侧由直线 y=1 描述。

奶牛 ii 从马路一侧的位置 (ai,0) 沿直线过马路到达另一侧的位置 (bi,1)。

所有 ai 互不相同，所有 bi 互不相同。

尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。

约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。

请帮助约翰计算安全奶牛的数量。

代码

import java.util.*;


public class Main {
    static class node implements Comparable<node> {
        int x, y;
        @Override
        public int compareTo(node o) {
            return x - o.x;
        }
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        int n;
        int[] suma = new int[100010];
        int[] sumb = new int[100010];
        node[] a = new node[100010];
        int ans = 0;
        n = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            a[i] = new node();
            a[i].x = inScanner.nextInt();
            a[i].y = inScanner.nextInt();;
        }
        Arrays.sort(a, 1, n + 1);
        suma[0] = -1000010;
        sumb[n + 1] = 1000010;
        for(int i = 1; i <= n; i ++)
            suma[i] = Math.max(suma[i - 1], a[i].y);
        for(int i = n; i >= 1; i --)
            sumb[i] = Math.min(sumb[i + 1], a[i].y);
        for(int i = 1; i <= n; i ++)
        {
            if(suma[i - 1] < a[i].y && a[i].y < sumb[i + 1])
                ans ++;
        }
        inScanner.close();
        System.out.println(ans);
    }
}
/*
4
-3 4
7 8
10 16
3 9
*/