current position:Home>leetcode 986. Interval List Intersections(python)
leetcode 986. Interval List Intersections(python)
2022-01-31 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] = [starti, endi] and secondList[j] = [startj, endj]. 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 <= starti < endi <= 109
- endi < starti+1
- 0 <= startj < endj <= 109
- endj < startj+1
analysis
According to the meaning , Given two closed interval lists ,firstList and secondList, among firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. 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 2-9 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 24-hour praise device, a case with a crawler skill, python crawler lesson 7-9
- 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