Problem 1


# 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 is a start time
		t <- Q.dequeue

		# if there is a tie in start times
		while == t.start_time:
			t <- max_end_time(t, Q.dequeue)
		# t is now the earliest starting time with maximum duration
	else is an end time

		# get latest end time
		while is an end time
			t <- Q.dequeue
		# t is now the latest end time
	add t's event to Events
	end if
end while


  • Sorting:
  • Loop:
  • ⇒ Total:


  • Base case
    1. Let the optimal solution
    2. Assume ’s is not the earliest start time……(1)
    3. Algorithm chooses earliest start time .
      1. is in total cover, but not in ’s cover.
      2. This means cannot be optimal. This is a contradiciton
      3. Thus Assumption (1) must be wrong
  • Inductive Step
    1. Let is the optimal solution
    2. ’s is the optimal next choice after
    3. Case 1: next item in priority queue is an end time
      1. Algorithm chooses where…
        1. among such points,
      2. Assume is an event that doesn’t satisfy the maximum endtime requirement……(2)
        1. Then, is in total cover, but not in ’s cover. This is a contradiction.
        2. Thus assumption (2) must be wrong
    4. Case 2: next item in priority queue is a start time
      1. Algorithm chooses with the earliest starting time and longest duration
      2. This is at least as optimal as , because…
        1. Thus the cover of is as large as
      3. Thus is as optimal as
  • QED

Problem 2

// 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 where has weight
    • Then, where has weight
  • 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 which is minimal


  • negating weights:
  • monotonically raising weights positive:
  • MST algorith:
  • Total: