时间复杂度

参考文献

JAVA 代码 解法1

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = 1000000;
        int[] arr = new int[N];
        int max = 0;
        int a = 0,b= 0,c=0,d=0;
        int n = sc.nextInt();
        for(int i=0;i<n;i++){
            a = sc.nextInt();
            b = sc.nextInt();
            if(b>max)max = b;
            // 没有包括b,是因为是点不是段
            for(int j=a;j<b;j++){
                arr[j]++;
            }
        }
        for(int i=0;i<n;i++){
            c = sc.nextInt();
            d = sc.nextInt();
            if(d>max)max = d;
            for(int j=c;j<d;j++){
                arr[j]++;
            }
        }
        int count = 0;
        for(int i =0;i<=max;i++){
            if(arr[i] ==2){
                count++;
                // System.out.println(i);
            }
        }
        System.out.println(count);
    }
}

JAVA 代码 解法2

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[1000000];
        int max = 0;
        int a = 0,b= 0;
        int n = sc.nextInt();
        for(int i=0;i<n*2;i++){
            a = sc.nextInt();
            b = sc.nextInt();
            if(b>max)max = b;
            // 没有包括b,是因为是点不是段
            for(int j=a;j<b;j++){
                arr[j]++;
            }
        }
        int count = 0;
        for(int i =0;i<=max;i++){
            if(arr[i]>1){
                count++;
            }
        }
        System.out.println(count);
    }
}