Overview
Distributed according to a leetcode topic, I want to realize the intersection and complement operation of the interval by myself, and then look at the source code of the related library (interval) to compare and learn
Self-actualization
Regardless of opening/closing/list display version
By default, all intervals are closed intervals on both sides
Intersection
def intersection(lis_one: list, lis_two: list):
# if not isinstance(lis_one, list) or not isinstance(lis_two, list):
# print("param_one and param_two should be list")
# return
# elif len(lis_one) != 2 or len(lis_two) != 2:
# print("the length of param_one and param_two should be 2")
# return
left = max(lis_one[0], lis_two[0])
right = min(lis_one[1], lis_two[1])
if left <= right:
return [left, right]
else:
return "empty"
print(intersection([1, 3], [2, 4])) # [2,3]
print(intersection([1, 4], [2, 3])) # [2,3]
print(intersection([1, 2], [3, 4])) # empty
Select the maximum value of the left value of two intervals and the minimum value of the right value. If there is an intersection, the intersection can be obtained directly; in the case of no intersection, the maximum value of the left value belongs to a larger interval, and the right value The minimum value of belongs to a small interval, then there will be left > right, which is used as the judgment standard
Union
def union(list_one, list_two):
left = min(list_one[0], list_two[0])
right = max(list_one[1], list_two[1])
other_left = max(list_one[0], list_two[0])
other_right = min(list_one[1], list_two[1])
if other_left > other_right:
return [left, other_right], [other_left, right]
else:
return [left, right]
print(union([1, 2], [3, 4])) # ([1, 2], [3, 4])
print(union([1, 4], [2, 3])) # [1, 4]
print(union([1, 3], [2, 4])) # [1, 4]
Complement
def ComplementarySet(larger_list, smaller_list):
# Verify that the second parameter is a subset of the first parameter
if intersection(larger_list, smaller_list) != smaller_list:
return '%s is not a subset of %s' % (repr(larger_list), repr(smaller_list))
fisrt_left = larger_list[0]
fisrt_right = smaller_list[0]
second_left = smaller_list[1]
second_right = larger_list[1]
first = [fisrt_left, fisrt_right]
second = [second_left, second_right]
if fisrt_left == fisrt_right:
first = None
if second_left == second_right:
second = None
if first and second:
return first, second
elif first:
return first
elif second:
return second
else:
return 'empty'
Implementation of interval library
The intersection of intervals is implemented by overloading the & amp; operator with __and__()
First judge whether the two objects to be intersected are the same, and if they are the same, return one directly
def __and__(self, other):
if self == other:
result = Interval()
result.lower_bound = self.lower_bound
result.upper_bound = self.upper_bound
result.lower_closed = self.lower_closed
result.upper_closed = self.upper_closed
Then use the built-in comes_before() function to determine the relative position, and then use the built-in overlaps() function to determine whether it overlaps. After clarifying the relative position and whether it overlaps, you can directly obtain the left and right boundaries of the intersection. The source code is as follows
# Use comes_before() to make self always the left interval
elif self. comes_before(other):
# Usually consider overlapping
if self. overlaps(other):
# determine intersection left boundary
if self.lower_bound == other.lower_bound:
lower = self. lower_bound
lower_closed = min(self.lower_closed, other.lower_closed)
elif self.lower_bound > other.lower_bound:
lower = self. lower_bound
lower_closed = self.lower_closed
else:
lower = other.lower_bound
lower_closed = other.lower_closed
# determine intersection right boundary
if self.upper_bound == other.upper_bound:
upper = self. upper_bound
upper_closed = min(self. upper_closed, other. upper_closed)
elif self.upper_bound < other.upper_bound:
upper = self. upper_bound
upper_closed = self. upper_closed
else:
upper = other. upper_bound
upper_closed = other. upper_closed
result = Interval(
lower, upper,
lower_closed=lower_closed, upper_closed=upper_closed)
# If there is no overlap, return an empty set directly
else:
result = Interval. none()
else:
result = other & self
return result
If a similar idea is implemented in the form above, it is as follows:
def innersection(list_one, list_two):
# Determine the relative position to the left
left_list = []
right_list = []
left = 0
if list_one[0] < list_two[0]:
left_list = list_one
right_list = list_two
elif list_one[0] > list_two[0]:
left_list = list_two
right_list = list_one
else:
return [list_one[0], min(list_one[1], list_two[1])]
# judge overlap
if left_list[1] < right_list[0]:
return "empty"
# In case of overlap
else:
left = right_list[0]
right = min(left_list[1], right_list[1])
return [left, right]
print(innersection([1, 4], [2, 3])) # [2, 3]
print(innersection([1, 2], [3, 4])) # empty
print(innersection([1, 3], [2, 4])) # [2, 3]
References
Leetcode original question
252. Meeting Room – LeetCode
Given an array intervals of a meeting schedule, each meeting time will include the start and end time intervals[i] = [starti, endi] , please judge whether a person can participate in all the meetings in it.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
output: false
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: true
hint:
0 <= intervals. length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106