import random

# jobScheduling2.py
#
# this is the same as jobScheduling.py except that it doesn't bother adding left endpoints
# to the sorted list nor the dictionary (since they'd ultimately be ignored anyway in the
# greedy endsFirst algorithm's loop)

# 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

# Takes a list of intervals as argument and creates a dictionary, whose keys
# are the endpoints of the intervals. Each endpoint maps to (i) the interval
# itself, (ii) whether or not the endpoint is a left endpoint or a 
# right endpoiont, and (iii) whether or not the interval is available for
# being used in the solution. Initially, all intervals are available.
def createDictionary(I):
  ptsToIntervals = {}
  for x in I:
    #ptsToIntervals[x[0]] = [x, "left"]
    ptsToIntervals[x[1]] = [x, "right"]

  printNow(ptsToIntervals)
  return ptsToIntervals

# Takes a list of intervals as argument and creates a sorted list of 
# endpoints of the intervals.
def createEndPtList(I):
  E = []
  for x in I:
    #E.append(x[0])
    E.append(x[1])
 
  E.sort()
  printNow(E)
  return E

# Scans the endpoints in left to right order, stops at each right endpoint
# and checks if corresponding interval is available, by checking if the 
# corresponding left endpoint is sufficiently to the right
def endsFirst(I):
  E = createEndPtList(I)
  ptsToIntervals = createDictionary(I)

  S = []
  minleft = -1;
  for pt in E:
    if((ptsToIntervals[pt][1] == "right")and(ptsToIntervals[pt][0][0] >= minleft)):
      S.append(ptsToIntervals[pt][0])
      minleft = pt

  return S