{"id":4768,"date":"2019-02-02T22:48:57","date_gmt":"2019-02-03T06:48:57","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4768"},"modified":"2019-02-02T22:49:22","modified_gmt":"2019-02-03T06:49:22","slug":"leetcode-986-interval-list-intersections","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-986-interval-list-intersections\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 986. Interval List Intersections"},"content":{"rendered":"\n

Given two lists of closed<\/strong> intervals, each list of intervals is pairwise disjoint and in sorted order.<\/p>\n\n\n\n

Return the intersection of these two interval lists.<\/p>\n\n\n\n

(Formally, a closed interval [a, b]<\/code> (with a <= b<\/code>) denotes the set of real numbers x<\/code> with a <= x <= b<\/code>.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]\nOutput: <\/strong>[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]\nReminder: <\/strong>The inputs and the desired output are lists of Interval objects, and not arrays or lists.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 0 <= A.length < 1000<\/code><\/li>
  2. 0 <= B.length < 1000<\/code><\/li>
  3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9<\/code><\/li><\/ol>\n\n\n\n
    Solution: Two pointers<\/strong><\/h2>\n\n\n\n
    Time complexity: O(m + n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 36 ms, 925.7 KB\nclass Solution {\npublic:\n  vector intervalIntersection(vector& A, vector& B) {\n    size_t i = 0;\n    size_t j = 0;\n    vector ans;\n    while (i < A.size() && j < B.size()) {\n      const int s = max(A[i].start, B[j].start);\n      const int e = min(A[i].end, B[j].end);\n      if (s <= e) ans.emplace_back(s, e);\n      if (A[i].end < B[j].end)\n        ++i;\n      else\n        ++j;\n    }\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua, running time: 96 ms, 7.6 MB\nclass Solution:\n  def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]':\n    i, j, ans = 0, 0, []\n    while i < len(A) and j < len(B):\n      s = max(A[i].start, B[j].start)\n      e = min(A[i].end, B[j].end)\n      if s <= e:\n        ans.append(Interval(s, e))\n      if A[i].end < B[j].end:\n        i += 1\n      else:\n        j += 1\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[284,128,177,175],"class_list":["post-4768","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-interval","tag-medium","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4768","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4768"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4768\/revisions"}],"predecessor-version":[{"id":4771,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4768\/revisions\/4771"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4768"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4768"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4768"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}