algo-en
  • Introduction
  • I. Dynamic Programming
    • Dynamic Programming in Details
    • Classic DP: Edit Distance
    • Classic DP: Super Egg
    • Classic DP: Super Egg(Advanced Solution)
    • Class DP: Longest Common Subsequence
    • Classis DP: Game Problems
    • Regular Expression
    • The Strategies of Subsequence Problem
    • Greedy: Interval Scheduling
    • 4 Keys Keyboard
    • What is DP Optimal Substructure
    • Longest Increasing Subsequence
    • KMP Algorithm In Detail
    • House Robber Problems
    • Stock Buy and Sell Problems
  • II. Data Structure
    • Binary Heap and Priority Queue
    • LRU Cache Strategy in Detail
    • Collections of Binary Search Operations
    • Special Data Structure: Monotonic Stack
    • Special Data Structure: Monotonic Stack
    • Design Twitter
    • Reverse Part of Linked List via Recursion
    • What's the Best Algo Book
    • Queue Implement Stack/Stack implement Queue
    • Framework for learning data structures and algorithms
  • III. Algorithmic thinking
    • My Way to Learn Algorithm
    • The Framework for Backtracking Algorithm
    • Binary Search in Detail
    • The Tech of Double Pointer
    • The Key Concept of TwoSum Problems
    • Divide Complicated Problem: Implement a Calculator
    • Prefix Sum Skill
    • FloodFill Algorithm in Detail
    • Interval Scheduling: Interval Merging
    • Interval Scheduling: Intersections of Intervals
    • String Multiplication
    • Pancake Soring Algorithm
    • Sliding Window Algorithm
    • Some Useful Bit Manipulations
    • Russian Doll Envelopes Problem
    • Recursion In Detail
    • Backtracking Solve Subset/Permutation/Combination
    • Several counter-intuitive Probability Problems
    • Shuffle Algorithm
  • IV. High Frequency Interview Problem
    • How to Implement LRU Cache
    • How to Find Prime Number Efficiently
    • How to Calculate Minimium Edit Distance
    • How to Solve Drop Water Problem
    • How to Remove Duplicate From Sorted Sequence
    • How to Find Longest Palindromic Substring
    • How to Reverse Linked List in K Group
    • How to Check the Validation of Parenthesis
    • How to Find Missing Element
    • How to Pick Elements From a Arbitrary Sequence
    • How to use Binary Search
    • How to Scheduling Seats
    • Union-Find Algorithm in Detail
    • Union-Find Application
    • Find Subsequence With Binary Search
    • Problems can be solved by one line
    • How to Find Duplicate and Missing Element
    • How to Check Palindromic LinkedList
  • V. Common Knowledge
    • Difference Between Process and Thread in Linux
    • You Must Know About Linux Shell
    • You Must Know About Cookie and Session
    • Cryptology Algorithm
    • Some Good Online Pratice Platforms
Powered by GitBook
On this page
  • Part One: Thought
  • Second Part: Code

Was this helpful?

  1. III. Algorithmic thinking

Interval Scheduling: Intersections of Intervals

PreviousInterval Scheduling: Interval MergingNextString Multiplication

Last updated 5 years ago

Was this helpful?

Translator:

Author:

This is the third article about the interval problem, and the last two articles respectively introduce the interval scheduling problem and the interval merging problem. Now, we will talk about the topic about how to find out interval intersection from two set of intervals efficiently.

【Leetcode 986】Interval List Intersections

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 xwith 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:

img
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:

  1. 0 <= A.length < 1000

  2. 0 <= B.length < 1000

  3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Part One: Thought

The general thought for interval problems is sorting first. Since question states that it has been ordered, then we can use two pointers to find out the intersections.

Here is the code:

# A, B like [[0,2],[5,10]...]
def intervalIntersection(A, B):
    i, j = 0, 0
    res = []
    while i < len(A) and j < len(B):
        # ...
        j += 1
        i += 1
    return res

Next, we will analyze all the situations or cases.

First, for two intervals, we use [a1,a2] and [b1,b2] to represent two intervals in the A and B respectively. So, let us find out how to make these two intervals don't have intersections.

It can be written in code like this:

if b2 < a1 or a2 < b1:
    [a1,a2] and [b1,b2] don't exist intersection

Then, what conditions should be met when two intervals exist intersection?

The negative proposition of the above logic is the condition.

# get a inverse direction of the sign of inequality, and change 'or' into 'and'
if b2 >= a1 and a2 >= b1:
    [a1,a2] and [b1,b2] exist intersection

Then, we enumerate all the situation that two intervals exist intersection.

It seems very simple: only four situation. exist. Then we should think about what's the common feather among these situations.

We surprisingly observe that the intersection of intervals get regular pattern. If the intersection is [c1,c2] then c1=max(a1,b1),c2=min(a2,b2)! Thus this observation is the key point of finding out the interaction. Now we make our code get further.

while i < len(A) and j < len(B):
    a1, a2 = A[i][0], A[i][1]
    b1, b2 = B[j][0], B[j][1]
    if b2 >= a1 and a2 >= b1:
        res.append([max(a1, b1), min(a2, b2)])
    # ...

Last step, it's surely that the pointer i and j will go forward, but when?

It's more understandable throught the gif that whether going forward only depends on the relationship between a2 andb2.

while i < len(A) and j < len(B):
    # ...
    if b2 < a2:
        j += 1
    else:
        i += 1

Second Part: Code

# A, B like [[0,2],[5,10]...]
def intervalIntersection(A, B):
    i, j = 0, 0 # double pointers
    res = []
    while i < len(A) and j < len(B):
        a1, a2 = A[i][0], A[i][1]
        b1, b2 = B[j][0], B[j][1]
        # two intervals have intersection
        if b2 >= a1 and a2 >= b1:
            # compute the intersection and add it into res
            res.append([max(a1, b1), min(a2, b2)])
        # Pointer go forward
        if b2 < a2: j += 1
        else:       i += 1
    return res

To give a brief summary, although the problem concerning intervals seems to be complicated, we can still use simple code to finish the task by observe common features between different situation.

GYHHAHA
labuladong