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 」
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].
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
Input: firstList = [[1,3],[5,9]], secondList =  Output:  Copy code
Input: firstList = , secondList = [[4,8],[10,12]] Output:  Copy code
Input: firstList = [[1,7]], secondList = [[3,10]] Output: [[3,7]] Copy code
- 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
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] < B[j] explain A[i] and B[j] There is no intersection ,i Add one for the next cycle Empathy B[j] < A[i] 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] < B[j] 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 .
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] < B[j]: i += 1 continue if B[j] < A[i]: j += 1 continue result.append([max(A[i], B[j]), min(A[i], B[j])]) if A[i] < B[j]: i += 1 else: j += 1 return result Copy code
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
You can also simplify the code , The principle of same .
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], B[j]) R = min(A[i], B[j]) if L<=R: result.append([L, R]) if A[i] < B[j]: i += 1 else: j += 1 return result Copy code
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
author[Wang Daya],Please bring the original link to reprint, thank you.
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
- 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