import random

# jobScheduling3.py
#
# this is the same as jobScheduling2.py (and jobscheduling.py) except that it also works
# correctly in the cases where the original two fail - that is, when some endpoint values
# appear in more than one interval.
#
# For example, if you do:
#    ints = [[1,3], [2,5], [4,6], [2.1,6]]
#
#    endsFirst(ints) will give the incorrect answer if using
# the versions in jobScheduling.py and jobScheduling2.py 
#
# The fix is simple: when filling the dictionary with interval data for right
# endpoints, only add the new associated   

# 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"]

    if ((x[1] in ptsToIntervals) and (x[0] < ptsToIntervals[x[1]][0][0])):
      printNow("dictionary already has smaller interval with same right end.")
      printNow("Ignoring: " + str(x))
    else:
      ptsToIntervals[x[1]] = [x, "right"]

  printNow(ptsToIntervals)
  for key in ptsToIntervals:
    printNow(key)
  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[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