区间列表交集

class Solution:
    def intersectionofintervals(self , first: List[List[int]], second: List[List[int]]) -> List[List[int]]:
        list1=[]
        count=0
        for i in range(len(first)):
            ins=0            
            for j in range(len(second)):
                #计算下次j的初始遍历位置
                if j>=count:
                    #print(i,j)
                    a=max(first[i][0],second[j][0])
                    b=min(first[i][-1],second[j][-1])
                    if a<=b:
                        ins=1
                        #print("有交集")
                        interval=[a,b]
                        #print(interval)
                        list1.append(interval)
                    else: #当第一次有交集之后，再次遇到无交集时直接后面的列表必定无交集就不用比较了，因此跳出j循环
                        #print("无交集")
                        if ins==1:
                            #下一个列表i直接从上一个列表的最后一个有交集列表处开始比较
                            count=j-1
                            break                   
        return list1

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param first int整型二维数组 
 * @param second int整型二维数组 
 * @return int整型二维数组
*/
func intersectionofintervals( first [][]int ,  second [][]int ) [][]int {
    ans:=[][]int{}
    for len(first)>0&&len(second)>0{
        if first[0][1]<second[0][0]{
            first=first[1:]
        }else if first[0][0]>second[0][1]{
            second=second[1:]
        }else{
            ans=append(ans,[]int{max(first[0][0],second[0][0]),min(first[0][1],second[0][1])})
            if first[0][1]<second[0][1]{
                first=first[1:]
            }else if first[0][1]>second[0][1]{
                second=second[1:]
            }else{
                first=first[1:]
                second=second[1:]
            }
        }
    }
    return ans
}

func min(a,b int)int{
    if a<b{
        return a
    }
    return b
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param first int整型vector<vector<>>
     * @param second int整型vector<vector<>>
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > intersectionofintervals(vector<vector<int> >& a,
            vector<vector<int> >& b) {
        vector<vector<int>>res;
        vector<pair<int, int>>c;
        for (auto x : a) {
            c.push_back({x[0], x[1]});
        }
        for (auto x : b) {
            c.push_back({x[0], x[1]});
        }
        sort(c.begin(), c.end());
        vector<int>ans;
        int l = c[0].first, r = c[0].second;
        for (int i = 1; i < c.size(); i++) {
            ans.clear();
            if (c[i].first <= r && c[i].second <= r) {
                ans.push_back(c[i].first);
                ans.push_back(c[i].second);
            } else if (c[i].first <= r) {
                ans.push_back(c[i].first);
                ans.push_back(r);
            }
            l = c[i].first;
            r=max(r,c[i].second);
            if(ans.size())res.push_back(ans);
        }
        return res;
    }
};

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param first int整型二维数组
# @param second int整型二维数组
# @return int整型二维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/20dce144f04f4db298fbb3349e9d93ec?tpId=196&tqId=40521&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        双指针遍历first、second两个列表，取交集。本题的关键在于取交集之后的区间移动问题。换句话说，first中的一个区间，可能与second中连续好几个区间都有交集，对于这种场景的处理，才是本题考查的关键。比如fisrt = [[1, 10]], second = [[0, 2], [3, 4], [6, 8]]，其交集为[[1, 2], [3, 4], [6, 8]]
    复杂度：
        时间复杂度：O(min(m, n))
        空间复杂度：O(1)
    """

    def intersectionofintervals(self, first, second):
        # write code here
        m, n = len(first), len(second)

        i, j = 0, 0
        x1, y1, x2, y2 = -1, -1, -1, -1
        res = []
        while i < m and j < n:
            x1, y1 = max(x1, first[i][0]), max(y1, first[i][1])  # 当前访问的first区间
            x2, y2 = max(x2, second[j][0]), max(y2,
                                                second[j][1])  # 当前访问的second区间

            if x1 <= x2:  # [x1, y1] 在 [x2, y2]左侧
                if y1 < x2:  # 无交集
                    i += 1
                else:  # y1 > x2，有交集，交集为 [x2, min(y1, y2)]
                    intersection = [x2, min(y1, y2)]
                    res.append(intersection)
                    if y1 == y2: # 区间移动
                        i += 1
                        j += 1
                    elif y1 > y2:
                        j += 1
                        x1 = y2
                    else:  # y1 < y2
                        i += 1
                        x2 = y1
            else:  # x1 > x2, [x2, y2] 在 [x1, y1]的左侧
                if y2 < x1:  # 无交集
                    j += 1
                else:  # y2 > x1，有交集，交集为 [x1, min(y1, y2)]
                    intersection = [x1, min(y1, y2)]
                    res.append(intersection)
                    if y1 == y2: # 区间移动
                        i += 1
                        j += 1
                    elif y1 < y2:
                        i += 1
                        x2 = y1
                    else:  # y1 > y2
                        j += 1
                        x1 = y2

        return res


if __name__ == "__main__":
    sol = Solution()

    first, second = [[0, 2], [5, 10], [11, 13]], [[1, 3], [5, 11]]

    res = sol.intersectionofintervals(first, second)

    print res

import java.util.*;


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) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // write code here
        int firstIndex = 0;
        int secondIndex = 0;

        while (firstIndex < first.size() && secondIndex < second.size()) {
            Integer firstStart = first.get(firstIndex).get(0);
            Integer firstEnd = first.get(firstIndex).get(1);

            Integer secondStart = second.get(secondIndex).get(0);
            Integer secondEnd = second.get(secondIndex).get(1);

            if (firstStart > secondEnd) {
                secondIndex++;
            } else if (firstEnd < secondStart) {
                firstIndex++;
            } else {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(Math.max(firstStart, secondStart));
                if (firstEnd < secondEnd) {
                    temp.add(firstEnd);
                    firstIndex++;
                } else {
                    temp.add(secondEnd);
                    secondIndex++;
                }
                result.add(temp);
            }
        }
        return result;
    }
}