题解 | #区间列表交集#

import java.util.*;

/**
 * NC390 区间列表交集
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param first int整型ArrayList<ArrayList<>>
     * @param second int整型ArrayList<ArrayList<>>
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> intersectionofintervals (ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second) {
        // return solution1(first,second);
        // return solution2(first,second);
        return solution3(first,second);
    }

    /**
     * 模拟法: 双指针
     * @param first
     * @param second
     * @return
     */
    private ArrayList<ArrayList<Integer>> solution1(ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second){
        int n1 = first.size();
        int n2 = second.size();

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> list;

        // 双指针
        int i = 0;
        int j = 0;
        int start1,end1,start2,end2;
        while(i<n1 && j<n2){
            start1 = first.get(i).get(0);
            end1 = first.get(i).get(1);
            start2 = second.get(j).get(0);
            end2 = second.get(j).get(1);
            if(start1 < start2){
                if(end1 < start2){
                    i++;
                }else{
                    if(end1 < end2){
                        list = new ArrayList<>();
                        list.add(start2);
                        list.add(end1);
                        result.add(list);
                        i++;
                    }else if(end1 > end2){
                        list = new ArrayList<>();
                        list.add(start2);
                        list.add(end2);
                        result.add(list);
                        j++;
                    }else{
                        list = new ArrayList<>();
                        list.add(start2);
                        list.add(end2);
                        result.add(list);
                        i++;
                        j++;
                    }
                }
            }
            else if(start1 > start2){
                if(end2 < start1){
                    j++;
                }else{
                    if(end2 < end1){
                        list = new ArrayList<>();
                        list.add(start1);
                        list.add(end2);
                        result.add(list);
                        j++;
                    }else if(end2 > end1){
                        list = new ArrayList<>();
                        list.add(start1);
                        list.add(end1);
                        result.add(list);
                        i++;
                    }else{
                        list = new ArrayList<>();
                        list.add(start1);
                        list.add(end1);
                        result.add(list);
                        i++;
                        j++;
                    }
                }
            }
            else{
                if(end1 < end2){
                    list = new ArrayList<>();
                    list.add(start2);
                    list.add(end1);
                    result.add(list);
                    i++;
                }else if(end1 > end2){
                    list = new ArrayList<>();
                    list.add(start2);
                    list.add(end2);
                    result.add(list);
                    j++;
                }else{
                    list = new ArrayList<>();
                    list.add(start2);
                    list.add(end2);
                    result.add(list);
                    i++;
                    j++;
                }
            }
        }

        return result;
    }

    /**
     * 模拟法: 双指针
     * 简化
     * 
     * @param first
     * @param second
     * @return
     */
    private ArrayList<ArrayList<Integer>> solution2(ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second){
        int n1 = first.size();
        int n2 = second.size();

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> list;

        // 双指针
        int i = 0;
        int j = 0;
        int start1,end1,start2,end2;
        while(i<n1 && j<n2){
            start1 = first.get(i).get(0);
            end1 = first.get(i).get(1);
            start2 = second.get(j).get(0);
            end2 = second.get(j).get(1);
            
            if(start1 <= start2){
                if(end1 < start2){
                    i++;
                }else{
                    if(end1 < end2){
                        list = new ArrayList<>();
                        list.add(start2);
                        list.add(end1);
                        result.add(list);
                        i++;
                    }else if(end1 > end2){
                        list = new ArrayList<>();
                        list.add(start2);
                        list.add(end2);
                        result.add(list);
                        j++;
                    }else{
                        list = new ArrayList<>();
                        list.add(start2);
                        list.add(end2);
                        result.add(list);
                        i++;
                        j++;
                    }
                }
            }else{
                if(end2 < start1){
                    j++;
                }else{
                    if(end2 < end1){
                        list = new ArrayList<>();
                        list.add(start1);
                        list.add(end2);
                        result.add(list);
                        j++;
                    }else if(end2 > end1){
                        list = new ArrayList<>();
                        list.add(start1);
                        list.add(end1);
                        result.add(list);
                        i++;
                    }else{
                        list = new ArrayList<>();
                        list.add(start1);
                        list.add(end1);
                        result.add(list);
                        i++;
                        j++;
                    }
                }
            }
        }

        return result;
    }

    /**
     * 模拟法: 双指针
     * 再简化
     * 
     * @param first
     * @param second
     * @return
     */
    private ArrayList<ArrayList<Integer>> solution3(ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second){
        int n1 = first.size();
        int n2 = second.size();

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> list;

        // 双指针
        int i = 0;
        int j = 0;
        int start1,end1,start2,end2;
        int left,right;
        while(i<n1 && j<n2){
            start1 = first.get(i).get(0);
            end1 = first.get(i).get(1);
            start2 = second.get(j).get(0);
            end2 = second.get(j).get(1);

            left = Math.max(start1,start2);
            right = Math.min(end1,end2);

            if(left <= right){
                list = new ArrayList<>();
                list.add(left);
                list.add(right);
                result.add(list);
            }

            if(end1 < end2){
                i++;
            }else if(end1 > end2){
                j++;
            }else{
                i++;
                j++;
            }
        }

        return result;
    }
}