import random

# Generates random intervals whose endpoints are in the range 0 through m (inclusive).
# The endpoints are reals and it is guaranteed that the right endpoint of each interval
# is at least as large as the left endpoint
def generateIntervals(n, m):
  I = []
  for i in range(0, n):
    x = []
    x.append(random.uniform(0, m))
    x.append(random.uniform(x[0], m))
    I.append(x)

  return I

# Calculates the length or span of an interval.
# Assumes that the right endpoint is at least as large as the left endpoint
def span(x):
  return x[1] - x[0]

# Returns true if x and y overlap
def overlap(x, y):
  if(x[0] <= y[0]):
    return (x[0] < y[0] < x[1])
  else:
    return (y[0] < x[0] < y[1])

# Returns the index of an interval in I with smallest span
def getMinSpanInterval(I):

  minSpanIndex = 0
  minSpan = I[0][1] - I[0][0]
  for i in range(1, len(I)):
    if(span(I[i]) < minSpan):
      minSpanIndex = i
      minSpan = span(I[i])

  return minSpanIndex

# Returns a subset of non-overlapping intervals obtaining by running the
# GREEDY_SPAN algorithm
def greedySpan(I):
  S = []

  # Repeatedly perform greedy step until no more requests are left
  # to process
  while(len(I) > 0):

    # Pick the interval from I with smallest span, delete from I and add to S
    i = getMinSpanInterval(I)
    y = I.pop(i)
    S.append(y)

    # Delete from I all intervals that overlap with the chosen interval
    # After this loop J will contain indices of intervals that overlap with y
    J = []
    for i in range(0, len(I)):
      if(overlap(I[i], y)):
        J.append(i)
	
    # Intervals with these indices are deleted from I
    # Note that indices are processed in decreasing order
    for i in range(len(J)-1, -1, -1):
      I.pop(J[i])

  return S

# Returns the degree of an interval x with respect to a set of intervals I
def degree(x, I):
  deg = 0

  # Scan all the intervals in I and count
  # 1 for every interval that overlaps x
  for y in I:
    if(overlap(x, y)):
      deg = deg + 1

  return deg - 1

# Returns the index of an interval in I with smallest degree
def getMinDegreeInterval(I):

  minDegreeIndex = 0
  minDegree = degree(I[0], I)

  for i in range(1, len(I)):
    if(degree(I[i], I) < minDegree):
      minDegreeIndex = i
      minDegree = degree(I[i], I)

  return minDegreeIndex


# Returns a subset of non-overlapping intervals obtaining by running the
# GREEDY_DEGREE algorithm
def greedyDegree(I):
  S = []

  # Repeatedly perform greedy step until no more requests are left
  # to process
  while(len(I) > 0):

    # Pick the interval from I with smallest span, delete from I and add to S
    i = getMinDegreeInterval(I)
    y = I.pop(i)
    S.append(y)

    # Delete from I all intervals that overlap with the chosen interval
    # After this loop J will contain indices of intervals that overlap with y
    J = []
    for i in range(0, len(I)):
      if(overlap(I[i], y)):
        J.append(i)

    # Intervals with these indices are deleted from I
    # Note that indices are processed in decreasing order
    for i in range(len(J)-1, -1, -1):
      I.pop(J[i])

  return S