current position：Home>leetcode 986. Interval List Intersections（python）
leetcode 986. Interval List Intersections（python）
20220131 19:01:55 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 18 God , Check out the activity details ：2021 One last more challenge 」
describe
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_{i}, end_{i}] and secondList[j] = [start_{j}, end_{j}]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
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 are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
Example 1:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Copy code
Example 2:
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
Copy code
Example 3:
Input: firstList = [], secondList = [[4,8],[10,12]]
Output: []
Copy code
Example 4:
Input: firstList = [[1,7]], secondList = [[3,10]]
Output: [[3,7]]
Copy code
Note:
 0 <= firstList.length, secondList.length <= 1000
 firstList.length + secondList.length >= 1
 0 <= start_{i} < end_{i} <= 109
 end_{i} < start_{i+1}
 0 <= start_{j} < end_{j} <= 109
 end_{j} < start_{j+1}
analysis
According to the meaning , Given two closed interval lists ,firstList and secondList, among firstList[i] = [start_{i}, end_{i}] and secondList[j] = [start_{j}, end_{j}]. Each interval list is disjoint in pairs , And sort them in order . The title asks us to return the intersection of these two interval lists .
The concepts of closed interval and intersection are also given in the title , Closed interval [a, b]（a <= b） For real numbers x Set ,a <= x <= b. The intersection of two closed intervals is a set of real numbers , They are either empty , Or expressed as a closed interval . for example ,[1, 3] and [2, 4] The intersection of [2, 3].
The idea is simple , Directly traverse all closed intervals to find the intersection ：

If A perhaps B There is an empty list , Return the empty list directly

Initialize two pointers i and j All for 0 , result result Empty list

When i Less than A And j Less than B The length of time has been carried out while loop
If A[i][1] < B[j][0] explain A[i] and B[j] There is no intersection ,i Add one for the next cycle Empathy B[j][1] < A[i][0] Also explain A[i] and B[j] There is no intersection ,j Add one for the next cycle If there is an intersection , Deposit it directly into result in If A[i][1] < B[j][1] Description needs to be viewed A[i+1] And B[j] Whether there is an intersection , therefore i Add one , otherwise j Add one , The same thing Copy code

Return to the end of the loop result that will do .
answer
class Solution(object):
def intervalIntersection(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
if not A or not B: return []
i = j = 0
result = []
while i < len(A) and j < len(B):
if A[i][1] < B[j][0]:
i += 1
continue
if B[j][1] < A[i][0]:
j += 1
continue
result.append([max(A[i][0], B[j][0]), min(A[i][1], B[j][1])])
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
Copy code
Running results
Runtime: 116 ms, faster than 90.07% of Python online submissions for Interval List Intersections.
Memory Usage: 14.3 MB, less than 69.98% of Python online submissions for Interval List Intersections.
Copy code
analysis
You can also simplify the code , The principle of same .
answer
class Solution(object):
def intervalIntersection(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
if not A or not B: return []
i = j = 0
result = []
while i < len(A) and j < len(B):
L = max(A[i][0], B[j][0])
R = min(A[i][1], B[j][1])
if L<=R:
result.append([L, R])
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
Copy code
Running results
Runtime: 112 ms, faster than 96.69% of Python online submissions for Interval List Intersections.
Memory Usage: 14.3 MB, less than 69.98% of Python online submissions for Interval List Intersections.
Copy code
Original link ：leetcode.com/problems/in…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311901537512.html
The sidebar is recommended
 Python  convert Matplotlib image to numpy Array or PIL Image
 Python and Java crawl personal blog information and export it to excel
 Using class decorators in Python
 Untested Python code is not far from crashing
 Python efficient derivation (8)
 Python requests Library
 leetcode 2047. Number of Valid Words in a Sentence（python）
 leetcode 2027. Minimum Moves to Convert String（python）
 How IOS developers learn Python Programming 5  data types 2
 leetcode 1971. Find if Path Exists in Graph（python）
guess what you like

leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores（python）

Python interface automation test framework (basic)  basic syntax

Detailed explanation of Python derivation

Python reptile lesson 29 Chinese monster database. It is found that there is a classification of color (he) desire (Xie) monsters during operation

A brief note on the method of creating Python virtual environment in Intranet Environment

[worth collecting] for Python beginners, sort out the common errors of beginners + Python Mini applet! (code attached)

[Python souvenir book] two people in one room have three meals and four seasons: 'how many years is it only XX years away from a hundred years of good marriage' ~?? Just come in and have a look.

The unknown side of Python functions

Python based interface automation test project, complete actual project, with source code sharing

A python artifact handles automatic chart color matching
Random recommended
 Python crawls the map of Gaode and the weather conditions of each city
 leetcode 1275. Find Winner on a Tic Tac Toe Game（python）
 leetcode 2016. Maximum Difference Between Increasing Elements（python）
 Run through Python date and time processing (Part 2)
 Application of urllib package in Python
 Django API Version (II)
 Python utility module playsound
 Database addition, deletion, modification and query of Python Sqlalchemy basic operation
 Tiobe November programming language ranking: Python surpasses C language to become the first! PHP is about to fall out of the top ten?
 Learn how to use opencv and python to realize face recognition!
 Using OpenCV and python to identify credit card numbers
 Principle of Python Apriori algorithm (11)
 Python AI steals your voice in 5 seconds
 A glance at Python's file processing (Part 1)
 Python cloud cat
 Python crawler actual combat, pyecharts module, python data analysis tells you which goods are popular on free fish~
 Using pandas to implement SQL group_ concat
 How IOS developers learn Python Programming 8  set type 3
 windows10+apache2. 4 + Django deployment
 Django parser
 leetcode 1560. Most Visited Sector in a Circular Track（python）
 leetcode 1995. Count Special Quadruplets（python）
 How to program based on interfaces using Python
 leetcode 1286. Iterator for Combination（python）
 leetcode 1418. Display Table of Food Orders in a Restaurant （python）
 Python Matplotlib drawing histogram
 Python development foundation summary (VII) database + FTP + character coding + source code security
 Python modular package management and import mechanism
 Django serialization (II)
 Python dataloader error "dataloader worker (PID XXX) is killed by signal" solution
 apache2. 4 + Django + windows 10 Automated Deployment
 leetcode 1222. Queens That Can Attack the King（python）
 leetcode 1387. Sort Integers by The Power Value （python）
 Tiger sniffing 24hour praise device, a case with a crawler skill, python crawler lesson 79
 Python object oriented programming 01: introduction classes and objects
 Baidu Post: high definition Python
 Python Matplotlib drawing contour map
 Python crawler actual combat, requests module, python realizes IMDB movie top data visualization
 Python classic: explain programming and development from simple to deep and step by step
 Python implements URL availability monitoring and instant push