AtCoder Beginner Contest 014 C - AtColor

いもす法再び

C - AtColor

問題文を読むと累積和を使うのかな？と思い、いもす法を使うことで解くことができました。

いもす法は前回勉強したことがあったので、助かりました。確か、yukicoderの括弧の問題でいもす法を始めて知ったと思います。

yamakasa3.hatenablog.com

yamakasa3.hatenablog.com

yukicoderの括弧の問題の解答がだいぶ込み入ってますが、imos法を使うことでもっときれいになるはずです。

いもす法について

いもす法 - いもす研 (imos laboratory)

考え方

を入店時間、 を出店時間と考えます。

また、絵具の種類を時刻に置き換え、絵具の種類のサイズの配列を用意します。

そして、いもす法を適用します。

コード

import java.util.Arrays;
import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int []a = new int[n];
        int []b = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = scan.nextInt();
            b[i] = scan.nextInt();
        }
        scan.close();

        // imos
        int []paint = new int[1000002];
        Arrays.fill(paint, 0);
        for(int i = 0; i < n; i++) {
            paint[a[i]] ++;
            paint[b[i] + 1] --;
        }
        for(int i = 1; i < 1000002; i++) {
            paint[i] += paint[i - 1];
        }

        int max = paint[0];
        for(int i = 1; i < 1000002; i++) {
            if(max < paint[i]) {
                max = paint[i];
            }
        }
        System.out.println(max);
    }
}