Say we are given the total size of the interval space. Say we are also given an array of tuples giving us the start and end indices of the interval to sum over along with a value. After completing all the sums, we would like to return the maximum element. How would I go about solving this efficiently?
Input format: n = interval space, intervals = array of tuples that contain start index, end index, and value to add to each element
Eg:
Input: n = 5, intervals = [(1,2,100),(2,5,100),(3,4,100)]
Output: 200
so array is initially [0,0,0,0,0]
At each iteration the following modifications will be made:
1) [100,100,0,0,0]
2) [100,200,100,100,100]
3) [100,200,200,200,100]
Thus the answer is 200.
All I've figured out so far is the brute force solution of splicing the array and adding a value to the spliced portion. How can I do better? Any help is appreciated!
One way is to separate your intervals into a beginning and an end, and specify how much is added or subtracted to the total based on whether you are in that interval or not. Once you sort the intervals based on their location on the number line, you traverse it, adding or subtracting the values based on whether you enter or leave the interval. Here is some code to do so:
def find_max_val(intervals):
operations = []
for i in intervals:
operations.append([i[0],i[2]])
operations.append([i[1]+1,-i[2]])
unique_ops = defaultdict(int)
for operation in operations:
unique_ops[operation[0]] += operation[1]
sorted_keys = sorted(unique_ops.keys())
print(unique_ops)
curr_val = unique_ops[sorted_keys[0]]
max_val = curr_val
for key in sorted_keys[1:]:
curr_val += unique_ops[key]
max_val = max(max_val, curr_val)
return max_val
intervals = [(1,2,100),(2,5,100),(3,4,100)]
print(find_max_val(intervals))
# Output: 200