TopCoder SRM595: LittleElephantAndIntervalsDiv1

まず、各区間ごとに異なる色で塗り分ける。
最後まで塗り分けたあと、残っている色数を X とすると、 X 個の色それぞれについて独立に白と黒の２色を割り当てられるので、\( 2^X \) が答えになる。

色が塗られていない部分を無視しないといけない点にだけ注意する。

public class LittleElephantAndIntervalsDiv1 {
    public long getNumber(int M, int[] L, int[] R) {
        var lastPaint = new int[M];
        for (int i = 0; i < L.Length; i++) {
            for (int j = L[i] - 1; j < R[i]; j++) {
                lastPaint[j] = i + 1;
            }
        }
        return (1L << lastPaint.Where(c => c > 0).Distinct().Count());
    }
}