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.

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.