ParentingPartnering.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

        int testCases = s.nextInt();
        int caseNum = 1;
        Solution p = new Solution();

        while (caseNum <= testCases) {
            int n = s.nextInt();
            int[][] a = new int[n][2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 2; j++)
                    a[i][j] = s.nextInt();
            }
            System.out.println(String.format("Case #%d: %s", caseNum, p.calSchedule(a)));

            caseNum++;
        }
    }

    private String calSchedule(int[][] scheudle) {
        if (scheudle == null || scheudle.length == 0 || scheudle[0].length == 0) {
            return null;
        }

        List<IntervalWithIndex> l = new ArrayList<>();
        for (int i = 0; i < scheudle.length; i++) {
            l.add(new IntervalWithIndex(scheudle[i][0], scheudle[i][1],i));
        }

        Collections.sort(l);

        int cEndTime = Integer.MIN_VALUE;
        int jEndTime = Integer.MIN_VALUE;

        char[] result = new char[l.size()];

        for (int i = 0; i < l.size(); i++) {
            IntervalWithIndex it = l.get(i);
            if (it.start >= cEndTime) {
                result[it.originalIndex] = 'C';
                cEndTime = it.end;
            } else if (it.start >= jEndTime) {
                result[it.originalIndex] = 'J';
                jEndTime = it.end;
            } else {
                return "IMPOSSIBLE";
            }
        }
        StringBuilder sb = new StringBuilder();
        for (char c : result) {
            sb.append(c);
        }

        return sb.toString();
    }

    private class IntervalWithIndex implements Comparable<IntervalWithIndex> {
        public int start;
        public int end;
        public int originalIndex;

        public IntervalWithIndex(int start, int end, int originalIndex) {
            this.start = start;
            this.end = end;
            this.originalIndex = originalIndex;
        }

        // natural ordering ascending
        public int compareTo(IntervalWithIndex t) {
            return this.start - t.start;
        }
    }
}