如何有效地检查两个时间范围是否重叠 (Python)
How to check if two time ranges are overlapping in an efficient manner (Python)
我有一个包含一组特定时间范围的列表：
['ARTS 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00', 'F', '02:00 - 12:00', 'COMP 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00']
现在，我希望将这些范围与另一组日期和日期范围进行比较：
['COMP 200 A', 'M', '09:30 - 11:30', 'W', '09:00 - 12:00']
如果有帮助，这里是字典的原始版本：
dict = {
'ARTS 111 A': {'course_code': 'ARTS 111 A', 'course_final': 'Fundam. of Drawing I', 'course_credits': '3 ',
'course_type': 'SBLOCK', 'course_room': 'S008', 'start_date': 'start:03/07/2022', 'days': 'M W',
'time': '09:00 - 12:00', 'instructor': 'John', 'capacity': '20', 'enrolled': '15', 'days_2': 'F',
'time_2': '02:00 - 12:00'
},
'COMP 111 A': {'course_code': 'COMP 111 A', 'course_final': 'Fundam. of Drawing I', 'course_credits': '3 ',
'course_type': 'SBLOCK', 'course_room': 'S008', 'start_date': 'start:03/07/2022', 'days': 'M W',
'time': '09:00 - 12:00', 'instructor': 'John', 'capacity': '20', 'enrolled': '15'}
}
clash = {
'SCI 100 A': {'course_code': 'SCI 100 A', 'course_final': 'Fundam. of Drawing I', 'course_credits': '3 ',
'course_type': 'SBLOCK', 'course_room': 'S008', 'start_date': 'start:03/07/2022', 'days': 'M W',
'time': '09:00 - 12:00', 'instructor': 'John', 'capacity': '20', 'enrolled': '15'}
}
我构建了以下函数，以便 'clean' 产生上述输出：
def date_time(dict):
lst = []
for x in dict:
lst.append(dict[x]['course_code'])
days = dict[x]['days']
days = days.split()
for y in days:
lst.append(y)
lst.append(dict[x]['time'])
return lst
显然，仅仅将这两者等同起来是行不通的。我正在创建一个时间表，用于检查预先存在的 class 之间的冲突，并将它们与用户希望 select 的新 class 进行比较。
希望对我需要做的事情提供一些帮助！
所以在工作和睡眠之后
我已经设法为您提供了解决方案
有一个函数可以将给定的列表分解为舒适的字典
然后是一个检查它们是否重叠的函数
exisitng_classes=['ARTS 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00', 'F',
'02:00 - 12:00', 'COMP 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00']
proposed_class=['COMP 200 A', 'M', '09:30 - 11:30', 'W', '09:00 - 12:00']
def check_time_overlap(time1,time2):
"""
returns boolean whether these times overlap or not, True if overlap
"""
split=time1.split("-")
min1=int(split[0].replace(":",""))
max1=int(split[-1].replace(":",""))
split=time2.split("-")
min2=int(split[0].replace(":",""))
max2=int(split[-1].replace(":",""))
return not ((max2 - min1) * (min2 - max1) >= 0)
def where_overlapping(existing,proposed):
"""
This function checks whether or not
and where the classes are overlapping
gets 1 list of all lessons and their hours
and 1 list of new single proposed lesson and its hours
returns a list of all overlaps, if empty = no overlaps
"""
name_of_class=""
sliced=existing[0].split(" ")[1:]
for item in sliced[:-1]:
name_of_class+=item+" "
name_of_class+=sliced[-1]
indexes=[]
counter=0
for each in existing:
if name_of_class in each:
indexes.append((counter,each))
counter+=1
class_dictionary={}
index=0
while index<len(indexes)-1:
class_dictionary[indexes[index][1]]=existing[indexes[index][0]+1:indexes[index+1][0]]
index+=1
class_dictionary[indexes[-1][1]]=existing[indexes[-1][0]+1:]
overlaps=[]
for classroom in class_dictionary:
prop_counter=0
while prop_counter<len(proposed[1:]):
counter=0
while counter<len(class_dictionary[classroom]):
if class_dictionary[classroom][counter]==proposed[1:][prop_counter]:
if check_time_overlap(class_dictionary[classroom][counter+1],proposed[1:][prop_counter+1]):
overlaps.append(classroom+" of "+ class_dictionary[classroom][counter+1]
+" with "+proposed[0]+" at "+proposed[1:][prop_counter+1]+" at day "
+proposed[1:][prop_counter])
counter+=2
prop_counter+=2
return overlaps
if __name__ == "__main__":
for x in where_overlapping(exisitng_classes,proposed_class):
print(x)
print(check_time_overlap("12:00 - 14:00","13:00-17:00"))
print(check_time_overlap("12:00 - 14:00","15:00-17:00"))
print(check_time_overlap("12:00 - 14:00","12:00-14:00"))
print(check_time_overlap("12:00 - 14:00","11:00-15:00"))
print(check_time_overlap("12:00 - 14:00","10:00-16:00"))
import datetime
import re
from dataclasses import dataclass, field
raw_data = ['ARTS 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00', 'F', '02:00 - 12:00',
'COMP 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00',
'COMP 200 A', 'M', '09:30 - 11:30', 'W', '09:00 - 12:00']
# the data is not structured, so let's parse it !
days_letters = ('M', 'T', 'W', 'H', 'F') # 'H' used for tHursday
timerange_pattern = re.compile(r"(\d\d):(\d\d) - (\d\d):(\d\d)")
# group(1) ^^^^ 2^^^^ 3^^^^ 4^^^^
coursename_pattern = re.compile(r"(\w+\s+\d+\s+\w)")
# group(1) ^^^^^^^^^^^^^^
@dataclass
class Course:
name: str
slots: list = field(default_factory=list)
@dataclass
class CourseSlot:
day: str
time_start: datetime.time
time_end: datetime.time
tokens = list(raw_data)
courses = []
while tokens:
token = tokens.pop(0) # get the first string
course_name_match = coursename_pattern.fullmatch(token)
assert course_name_match is not None
course_name = course_name_match.group(1)
course = Course(name=course_name)
# then read the days and hours
while tokens:
if tokens[0] in days_letters:
day = tokens.pop(0)
timerange_match = timerange_pattern.fullmatch(tokens.pop(0))
assert timerange_match is not None
start_hour = int(timerange_match.group(1))
start_minute = int(timerange_match.group(2))
end_hour = int(timerange_match.group(3))
end_minute = int(timerange_match.group(4))
course.slots.append(CourseSlot(
day=day,
time_start=datetime.time(hour=start_hour, minute=start_minute),
time_end=datetime.time(hour=end_hour, minute=end_minute),
))
else:
break
courses.append(course)
print(courses)
# [Course(name='ARTS 111 A', slots=[CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# CourseSlot(day='F', time_start=datetime.time(2, 0), time_end=datetime.time(12, 0))]),
# Course(name='COMP 111 A', slots=[CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))]),
# Course(name='COMP 200 A', slots=[CourseSlot(day='M', time_start=datetime.time(9, 30), time_end=datetime.time(11, 30)),
# CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))])]
@dataclass
class Clash:
course1_name: str
course2_name: str
course1_slot: CourseSlot
course2_slot: CourseSlot
# now search for overlap :
clashes = []
for i, first_course in enumerate(courses[:-1], start=1): # from first to last-1
for second_course in courses[i:]: # from after the first to the last
for first_slot in first_course.slots:
for second_slot in second_course.slots:
if first_slot.day == second_slot.day:
if first_slot.time_start <= second_slot.time_end and \
second_slot.time_start <= first_slot.time_end: # see
# we have a match !
clashes.append(Clash(course1_name=first_course.name,
course2_name=second_course.name,
course1_slot=first_slot,
course2_slot=second_slot))
print(clashes)
# [
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 111 A',
# course1_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# ),
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 111 A',
# course1_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# ),
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='M', time_start=datetime.time(9, 30), time_end=datetime.time(11, 30))
# ),
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# ),
# Clash(course1_name='COMP 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='M', time_start=datetime.time(9, 30), time_end=datetime.time(11, 30))
# ),
# Clash(course1_name='COMP 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# )
# ]
我有一个包含一组特定时间范围的列表：
['ARTS 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00', 'F', '02:00 - 12:00', 'COMP 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00']
现在，我希望将这些范围与另一组日期和日期范围进行比较：
['COMP 200 A', 'M', '09:30 - 11:30', 'W', '09:00 - 12:00']
如果有帮助，这里是字典的原始版本：
dict = {
'ARTS 111 A': {'course_code': 'ARTS 111 A', 'course_final': 'Fundam. of Drawing I', 'course_credits': '3 ',
'course_type': 'SBLOCK', 'course_room': 'S008', 'start_date': 'start:03/07/2022', 'days': 'M W',
'time': '09:00 - 12:00', 'instructor': 'John', 'capacity': '20', 'enrolled': '15', 'days_2': 'F',
'time_2': '02:00 - 12:00'
},
'COMP 111 A': {'course_code': 'COMP 111 A', 'course_final': 'Fundam. of Drawing I', 'course_credits': '3 ',
'course_type': 'SBLOCK', 'course_room': 'S008', 'start_date': 'start:03/07/2022', 'days': 'M W',
'time': '09:00 - 12:00', 'instructor': 'John', 'capacity': '20', 'enrolled': '15'}
}
clash = {
'SCI 100 A': {'course_code': 'SCI 100 A', 'course_final': 'Fundam. of Drawing I', 'course_credits': '3 ',
'course_type': 'SBLOCK', 'course_room': 'S008', 'start_date': 'start:03/07/2022', 'days': 'M W',
'time': '09:00 - 12:00', 'instructor': 'John', 'capacity': '20', 'enrolled': '15'}
}
我构建了以下函数，以便 'clean' 产生上述输出：
def date_time(dict):
lst = []
for x in dict:
lst.append(dict[x]['course_code'])
days = dict[x]['days']
days = days.split()
for y in days:
lst.append(y)
lst.append(dict[x]['time'])
return lst
显然，仅仅将这两者等同起来是行不通的。我正在创建一个时间表，用于检查预先存在的 class 之间的冲突，并将它们与用户希望 select 的新 class 进行比较。 希望对我需要做的事情提供一些帮助！
所以在工作和睡眠之后 我已经设法为您提供了解决方案 有一个函数可以将给定的列表分解为舒适的字典 然后是一个检查它们是否重叠的函数
exisitng_classes=['ARTS 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00', 'F',
'02:00 - 12:00', 'COMP 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00']
proposed_class=['COMP 200 A', 'M', '09:30 - 11:30', 'W', '09:00 - 12:00']
def check_time_overlap(time1,time2):
"""
returns boolean whether these times overlap or not, True if overlap
"""
split=time1.split("-")
min1=int(split[0].replace(":",""))
max1=int(split[-1].replace(":",""))
split=time2.split("-")
min2=int(split[0].replace(":",""))
max2=int(split[-1].replace(":",""))
return not ((max2 - min1) * (min2 - max1) >= 0)
def where_overlapping(existing,proposed):
"""
This function checks whether or not
and where the classes are overlapping
gets 1 list of all lessons and their hours
and 1 list of new single proposed lesson and its hours
returns a list of all overlaps, if empty = no overlaps
"""
name_of_class=""
sliced=existing[0].split(" ")[1:]
for item in sliced[:-1]:
name_of_class+=item+" "
name_of_class+=sliced[-1]
indexes=[]
counter=0
for each in existing:
if name_of_class in each:
indexes.append((counter,each))
counter+=1
class_dictionary={}
index=0
while index<len(indexes)-1:
class_dictionary[indexes[index][1]]=existing[indexes[index][0]+1:indexes[index+1][0]]
index+=1
class_dictionary[indexes[-1][1]]=existing[indexes[-1][0]+1:]
overlaps=[]
for classroom in class_dictionary:
prop_counter=0
while prop_counter<len(proposed[1:]):
counter=0
while counter<len(class_dictionary[classroom]):
if class_dictionary[classroom][counter]==proposed[1:][prop_counter]:
if check_time_overlap(class_dictionary[classroom][counter+1],proposed[1:][prop_counter+1]):
overlaps.append(classroom+" of "+ class_dictionary[classroom][counter+1]
+" with "+proposed[0]+" at "+proposed[1:][prop_counter+1]+" at day "
+proposed[1:][prop_counter])
counter+=2
prop_counter+=2
return overlaps
if __name__ == "__main__":
for x in where_overlapping(exisitng_classes,proposed_class):
print(x)
print(check_time_overlap("12:00 - 14:00","13:00-17:00"))
print(check_time_overlap("12:00 - 14:00","15:00-17:00"))
print(check_time_overlap("12:00 - 14:00","12:00-14:00"))
print(check_time_overlap("12:00 - 14:00","11:00-15:00"))
print(check_time_overlap("12:00 - 14:00","10:00-16:00"))
import datetime
import re
from dataclasses import dataclass, field
raw_data = ['ARTS 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00', 'F', '02:00 - 12:00',
'COMP 111 A', 'M', '09:00 - 12:00', 'W', '09:00 - 12:00',
'COMP 200 A', 'M', '09:30 - 11:30', 'W', '09:00 - 12:00']
# the data is not structured, so let's parse it !
days_letters = ('M', 'T', 'W', 'H', 'F') # 'H' used for tHursday
timerange_pattern = re.compile(r"(\d\d):(\d\d) - (\d\d):(\d\d)")
# group(1) ^^^^ 2^^^^ 3^^^^ 4^^^^
coursename_pattern = re.compile(r"(\w+\s+\d+\s+\w)")
# group(1) ^^^^^^^^^^^^^^
@dataclass
class Course:
name: str
slots: list = field(default_factory=list)
@dataclass
class CourseSlot:
day: str
time_start: datetime.time
time_end: datetime.time
tokens = list(raw_data)
courses = []
while tokens:
token = tokens.pop(0) # get the first string
course_name_match = coursename_pattern.fullmatch(token)
assert course_name_match is not None
course_name = course_name_match.group(1)
course = Course(name=course_name)
# then read the days and hours
while tokens:
if tokens[0] in days_letters:
day = tokens.pop(0)
timerange_match = timerange_pattern.fullmatch(tokens.pop(0))
assert timerange_match is not None
start_hour = int(timerange_match.group(1))
start_minute = int(timerange_match.group(2))
end_hour = int(timerange_match.group(3))
end_minute = int(timerange_match.group(4))
course.slots.append(CourseSlot(
day=day,
time_start=datetime.time(hour=start_hour, minute=start_minute),
time_end=datetime.time(hour=end_hour, minute=end_minute),
))
else:
break
courses.append(course)
print(courses)
# [Course(name='ARTS 111 A', slots=[CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# CourseSlot(day='F', time_start=datetime.time(2, 0), time_end=datetime.time(12, 0))]),
# Course(name='COMP 111 A', slots=[CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))]),
# Course(name='COMP 200 A', slots=[CourseSlot(day='M', time_start=datetime.time(9, 30), time_end=datetime.time(11, 30)),
# CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))])]
@dataclass
class Clash:
course1_name: str
course2_name: str
course1_slot: CourseSlot
course2_slot: CourseSlot
# now search for overlap :
clashes = []
for i, first_course in enumerate(courses[:-1], start=1): # from first to last-1
for second_course in courses[i:]: # from after the first to the last
for first_slot in first_course.slots:
for second_slot in second_course.slots:
if first_slot.day == second_slot.day:
if first_slot.time_start <= second_slot.time_end and \
second_slot.time_start <= first_slot.time_end: # see
# we have a match !
clashes.append(Clash(course1_name=first_course.name,
course2_name=second_course.name,
course1_slot=first_slot,
course2_slot=second_slot))
print(clashes)
# [
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 111 A',
# course1_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# ),
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 111 A',
# course1_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# ),
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='M', time_start=datetime.time(9, 30), time_end=datetime.time(11, 30))
# ),
# Clash(course1_name='ARTS 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# ),
# Clash(course1_name='COMP 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='M', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='M', time_start=datetime.time(9, 30), time_end=datetime.time(11, 30))
# ),
# Clash(course1_name='COMP 111 A',
# course2_name='COMP 200 A',
# course1_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0)),
# course2_slot=CourseSlot(day='W', time_start=datetime.time(9, 0), time_end=datetime.time(12, 0))
# )
# ]