# each item is in format (time, start/end, event_index)# order priosity: smaller time -> start ->Q = sort(L, R)Events = []while Q has elements: if Q.next is a start time t <- Q.dequeue # if there is a tie in start times while Q.next.start_time == t.start_time: t <- max_end_time(t, Q.dequeue) # t is now the earliest starting time with maximum duration else Q.next is an end time # get latest end time while Q.next is an end time t <- Q.dequeue # t is now the latest end time add t's event to Events end ifend while
// Idea: Reverse the order of weights in the graph,// then run minimum spanning tree.// First, reverse the weight ordering of the graph// negate weights...for e in E e' <- e e'.weight <- -e.weight add e' to E'let m be the edge with minimum weight in E'// then monotonically increase so all weights are positive // (to use MST algorithm)for e in E' e'.weight += m.weight + 1// Then, run MST algorithm (Prim or Kruskal)V_mst, E_mst <- MST(V, E')// the minimum spanning tree in (V, E') is// same as the maximum spanning tree in (V, E)// Return the edges that are not in the MST.return E \ E_mst
The problem is equivalent to getting a tree whose sum of edge weights is maximal.
This is because the remaining graph must be acyclic (a tree) and…
…because the sum of removed weights is minimal thus the sum of remaining weights must be maximal.
We can convert the original graph in question to a weight order reversed graph:
Suppose E={e1,e2,…,em} where ei has weight wi
Then, E′={e1′,…em′} where ei′ has weight wm−i+1
Then, we can leverage the correctness of the MST algorithm (prim’s or kruskal’s) in order to get the minimum spanning tree of this new weight-order-reversed-graph.
The edges in this MST is the maximum spanning tree in the original graph
Therefore, removing these edges we are left with the subset F which is minimal