ABC-014-C AtColor

■■■問題■■■

AtColor社は，0から1000000まで1000001通りの濃さがある灰色の絵の具を販売することにしました．
0が最も黒く，1000000が最も白い絵の具です．

しかし，途方も無い数の濃さのバリエーションがある一方，
消費者には細かい違いが分からないということが判明しました．
これを知ったAtColor社は，売れない濃さの絵の具を生産するのはやめて，
最も人気のある濃さの色の絵の具1つだけを販売することにしました．

AtColor社は上記を達成するために，
最も人気な絵の具がどのくらい売れるかをアンケート調査で調べることにしました．
AtColor社がどの範囲の濃さの絵の具なら購入したいかというアンケートを消費者に対して行ったところ，
「a <= x <= b を満たす濃さxの絵の具ならば購入する」という形式の情報がn件得られました．

あなたの仕事は，これらの情報から，
最も多くの消費者に購入される濃さの絵の具について，
その絵の具を購入する消費者の数を出力するプログラムを作ることです．

■■■入力■■■

n
a1 b1
a2 b2
・
・
・
an bn

●1行目には，アンケート情報の数 n(1 <= n <= 10万) が与えられる．
●2行目からn行は，各アンケート情報を表す．
  ai,bi(0 <= ai <= bi <= 100万) は
  それぞれi番目のアンケート情報における濃さの下限と上限(端を含む)を表す整数で，
  空白区切りで与えられる．

■■■出力■■■

最も多くの消費者に購入される濃さの絵の具について，
それを購入する消費者の数を1行に出力せよ．
出力の末尾に改行を入れること．

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            WillReturn.Add("0 2");
            WillReturn.Add("2 3");
            WillReturn.Add("2 4");
            WillReturn.Add("5 6");
            //3
            //●濃さ0,1,4,5,6 の絵の具は，1人の消費者によって購入してもらえます．
            //●濃さ2の絵の具は，3人の消費者によって購入してもらえます．
            //●濃さ3の絵の具は，2人の消費者によって購入してもらえます．
            //●他の濃さの絵の具は誰にも購入してもらえません．
            //よって，3を出力します．
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1000000 1000000");
            WillReturn.Add("1000000 1000000");
            WillReturn.Add("0 1000000");
            WillReturn.Add("1 1000000");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] CntArr = new int[1000001];
        int UB = CntArr.GetUpperBound(0);

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            int StaInd = wkArr[0];
            int EndInd = wkArr[1];
            CntArr[StaInd]++;
            if (EndInd < UB) CntArr[EndInd + 1]--;
        }

        int Answer = int.MinValue;
        int RunSum = 0;
        for (int I = 0; I <= UB; I++) {
            RunSum += CntArr[I];
            if (Answer < RunSum)
                Answer = RunSum;
        }
        Console.WriteLine(Answer);
    }
}

解説

いもす法で解いてます。