# Posts tagged as “intersection”

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b.

We remove the intersections between any interval in intervals and the interval toBeRemoved.

Return a sorted list of intervals after all such removals.

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]


Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]


Constraints:

• 1 <= intervals.length <= 10^4
• -10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

## Solution: Geometry

Time complexity: O(n)
Space complexity: O(n)

# Problem

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

# Solution1: Hashtable

Time complexity: O(m + n)

Space complexity: O(m)

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

C++ using std::set_intersection

C++ hashtable

Problem:

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Example 2:

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

1. schedule and schedule[i] are lists with lengths in range [1, 50].
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.

Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

Related Problems:

Mission News Theme by Compete Themes.