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 interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. 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].)
Example 1:
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
Note:
0 <= A.length < 10000 <= B.length < 10000 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
Solution: Two pointers
Time complexity: O(m + n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, running time: 36 ms, 925.7 KB class Solution { public: vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) { size_t i = 0; size_t j = 0; vector<Interval> ans; while (i < A.size() && j < B.size()) { const int s = max(A[i].start, B[j].start); const int e = min(A[i].end, B[j].end); if (s <= e) ans.emplace_back(s, e); if (A[i].end < B[j].end) ++i; else ++j; } return ans; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Author: Huahua, running time: 96 ms, 7.6 MB class Solution: def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]': i, j, ans = 0, 0, [] while i < len(A) and j < len(B): s = max(A[i].start, B[j].start) e = min(A[i].end, B[j].end) if s <= e: ans.append(Interval(s, e)) if A[i].end < B[j].end: i += 1 else: j += 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment