Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
cut, merge and intersection (combination) solution in Clear category for Lightbulb More by kdim
from datetime import datetime, timedelta
from itertools import combinations
from typing import List, Optional, Union, Tuple
def cut_operating(intervals, operating): # cut the intervals according to the duration of the lamp
inters = []
for i, j in intervals:
if operating < j - i:
return inters + [[i, i + operating]]
operating -= j - i
inters += [[i, j]]
return inters
def merge_intervals(intervals, req): # merge the intervals according to required lamps
intervals = sorted(intervals)
merge = [[datetime.min, datetime.min]]
for interval in combinations(intervals, req): # combination of intervals with a quantity of "req"
minim = max(i for i, j in interval) # start intersection of intervals
maxim = min(j for i, j in interval) # end intersection of intervals
last = merge[-1]
if maxim > last[1] >= minim:
last[1] = maxim
elif maxim > minim > last[1]:
merge += [[minim, maxim]]
return merge
def sum_light(els: List[Union[datetime, Tuple[datetime, int]]],
start_watching: Optional[datetime] = datetime.min,
end_watching: Optional[datetime] = datetime.max,
operating: Optional[timedelta] = timedelta.max,
req: Optional[int] = 1) -> int:
els = [i if type(i) == tuple else (i, 1) for i in els] # normalisation of array
lamps = max(j for i, j in els) # number of the lamps
intervals = []
for lamp in range(1, lamps + 1): # for every lamp get intervals of light
interval = [i for i, j in els if j == lamp] + [datetime.max]
interval = [[i, j] for i, j in zip(interval[::2], interval[1::2])]
intervals += cut_operating(interval, operating) # for every lamp cut intervals according duration
# filter intervals according start and stop watching
intervals = [[i, j] for i, j in merge_intervals(intervals, req) if i < end_watching and j > start_watching]
if not intervals:
return 0
intervals[0][0] = max(intervals[0][0], start_watching) # cut with start
intervals[-1][1] = min(intervals[-1][1], end_watching) # cut with end
return sum([(j - i).total_seconds() for i, j in intervals])
Feb. 2, 2021