public class AD {
    int start;
    int end;
    boolean status = false; //true : on, false: pause

    AD(int s, int e, boolean st) {
        this.start = s;
        this.end = e;
        this.status = st;
    }
}




    public static void main(String[] args) {
        AD[] ads = new AD[]{
                new AD(1, 9, true),
                new AD(2, 5, false),
                new AD(10, 15, true),
                new AD(13, 18, false),
                new AD(17, 20, true)
        };
        List<AD> onADs = new ArrayList<>();
        List<AD> pauseADs = new ArrayList<>();
        for (int i = 0; i < ads.length; i++) {
            if (ads[i].status) {
                onADs.add(ads[i]);
            } else {
                pauseADs.add(ads[i]);
            }
        }
        List<AD> onSeg = new ArrayList<>();
        int pI = 0, oI = 0;
        while (oI < onADs.size()) {
            AD on = onADs.get(oI);
            if (pI >= pauseADs.size()) {
                onSeg.add(new AD(on.start, on.end, true));
                oI++;
            } else {
                AD pa = pauseADs.get(pI);
                if (pa.start > on.end) {  //case 1 沒交集
                    System.out.println(1);
                    onSeg.add(new AD(on.start, on.end, true));
                    oI++;
                } else if (pa.end < on.start) { // case 2 沒交集
                    System.out.println(2);
                    pI++;
                } else if (on.start < pa.start && on.end < pa.end) { //case 3 on end > p start
                    System.out.println(3);
                    onSeg.add(new AD(on.start, pa.start - 1, true));
                    oI++;
                } else if (on.start > pa.start && pa.end > on.start && on.end > pa.end) { //case 4 p end > on start
                    System.out.println(4);
                    onSeg.add(new AD(pa.end + 1, on.end, true));
                    oI++;
                } else if (on.start > pa.start && on.end < pa.end) { // case 5 whole on seg  in  pa seg
                    System.out.println(5);
                    oI++;
                } else if (on.start < pa.start && on.end > pa.end) { // case 5 whole pa seg  in  on seg
                    System.out.println(6);
                    onSeg.add(new AD(on.start, pa.start - 1, true));
                    onSeg.add(new AD(pa.end + 1, on.end, true));
                    oI++;
                    pI++;
                }
            }
        }
        for (int i = 0; i < onSeg.size(); i++) {
            AD aa = onSeg.get(i);
            System.out.println(aa.start + " " + aa.end);
        }
    }

1 1
6 9
10 12
19 20