# Résolution de problèmes algorithmiques

Maintain a set, allowing to add or remove elements and to query the sum of the up to k largest items.

# Use two heaps

The idea is to use 2 heaps. We will use a min-heap ‘large’, where the top element is its smallest item. As well as a max-heap ‘small’, where the top element is its largest item.

large:            small:
[800, 400, 350]   [200, 100]
^top    ^top
<-----k------->


The invariant is that if the set contains less than k items, then it is entirely stored in ‘large’, while ‘small’ is empty. Otherwise ‘large’ stores the k largest items of the set, and ‘small’ all the others.

Maintaining the invariant, simply consists to move items from one heap to another, if the cardinality of the large set is not k.

# Application

In the above mentioned problem, we are given n weighted intervals, and need to find a set of up to k intervals, all intersecting, maximizing the total weight of this set. This can be solved by a sweep line algorithm. Just scan the intervals from left to right, adding or removing weights to a dynamic set, when the endpoints of the corresponding intervals are processed. Fairly easy. Hence overall time complexity is O(n log n).

# Implementation in Python

Here we use our implementation of lazy heaps, explained here.