Created
October 17, 2021 18:31
-
-
Save MatteoLacki/9bf30e8ea81b786e068458fc7469a033 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
A single thread function to get the total amount of time spent being insured. | |
""" | |
def get_time_being_insured(intervals) -> float: | |
"""Get the time being insured""" | |
events = [] | |
for start, end in intervals: | |
events.append((start, 1 )) | |
events.append((end, -1 )) | |
# Sorting by occurences of events | |
# second coordinate distinguishes start (1) from end (0) | |
sorted_events = sorted(events, key=lambda x: x[0]) | |
# now we do a simple line swipe: | |
# starting from earliest event till last even. | |
# we add up differences between times of consecutive events | |
# only if currently we are inside some interval | |
opened_intervals = 1 # until current moment excluding it. | |
time_insured = 0.0 | |
prev_time, _ = sorted_events[0] | |
for time, opening_or_closing_of_interval in sorted_events[1:]: | |
if opened_intervals: | |
time_insured += time - prev_time | |
opened_intervals += opening_or_closing_of_interval | |
prev_time = time | |
return time_insured | |
if __name__ == "__main__": | |
# some small test case | |
starts = [10, 30, 20, 50, 100] | |
ends = [24, 59, 26, 52, 105] | |
# [10, 24] or [30, 59] or [20, 26] or [50, 52] or [100, 105] | |
# = | |
# [10, 26] or [30, 59] or [100, 105] | |
intervals = list(zip(starts, ends)) # no need for 'list' except printing | |
print("Trying to get total time of being insured with intervals:") | |
for start, end in intervals: | |
print(f"[{start} : {end}]") | |
print(f"Expecting interval to span 16 + 29 + 5 = 50") | |
print("Getting:") | |
print(get_time_being_insured(intervals)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment