title: Why does my solution to problem 3 of the CodeJam 2020 Qualification Round not work?
body: <p>I would like to receive help in understanding why my solution to Problem 3 of the Google CodeJam 2020 Qualifier does not work. </p>
  
  <p>Link to problem: <a href="https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9" rel="nofollow noreferrer">https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9</a></p>
  
  <p>My solution:</p>
  
  <p>High-level overview:</p>
  
  <ul>
  <li>take input</li>
  <li>figure out if the given input is impossible by sorting according to start times and then checking if more than 2 subsequent activities are 'active' at once (which is impossible)</li>
  <li>if it is, output accordingly; if it isn't, proceed with the procedure below</li>
  <li>arbitrarily assign the first person: in my solution I choose Cameron (C).</li>
  <li>next, since we know that a solution exists, and the array I iterate through is sorted according to start times, if the very next activity interval (chronologically) overlaps in its duration with the current, assign it to the person who is not currently busy. This is purely because a solution exists, and it clearly cannot be the current person, so it must be the other.</li>
  <li>moreover, if the very next activity interval (chronologically) does not overlap with the current activity, then assign it to the person who is currently busy (because he will not be busy for the next activity)</li>
  <li>in addition, quoted directly from the problem's official analysis: "If an assignment is possible, there cannot be any set of three activities that pairwise overlap, so by the contrapositive of the the previous argument, we will be able to assign the activity to at least one of Jamie or Cameron at every step."</li>
  </ul>
  
  <p>At this moment, I believe that these arguments suffice to show that my logic is valid, although my code evidently does not always produce the correct answer. I would greatly appreciate any help on this, since I have spent hours trying to debug, un-reason, or find a counter-example to my code to no avail. I have included my code, for reference, below.</p>
  
  <p>Code:</p>
  
  <pre><code>
  for p in range(int(input())):
  
      s = int(input())
      l = []
      for i in range(s):
          l.append(list(map(int, list(input().split()))))
      unsort = l.copy()
      l = sorted(l, key=lambda tup: (tup[0],tup[1]))
      enumerated = list(enumerate(unsort))
      enumerated.sort(key=lambda x: x[1][0])
      impossible = False
      endings = sorted([(x[1], False) for x in unsort])
      startings = sorted([(x[0], True) for x in unsort])
      total = sorted(endings + startings, key=lambda tup: (tup[0], tup[1]))
  
      size = 0
  
      for i in total:
          if i[1] == True:
              size += 1
          else:
              size -= 1
          if size &gt; 2:
              impossible = True
  
  
  
  
      def overlap(a,b):
          if not max(a[0], b[0]) &gt;= min(a[1], b[1]):
              return True
          else:
              return False
  
      ans = "C"
  
      def opp(a):
          if a == "C":
              return "J"
          else:
              return "C"
  
  
      if impossible == True:
         print("Case #" + str(p+1) + ": " + "IMPOSSIBLE")
  
      else:
          for i in range(0, s-1):
              if overlap(l[i], l[i+1]) == True:
                  ans = ans + opp(ans[len(ans)-1])
  
              else:
                  ans = ans + opp(opp(ans[len(ans)-1]))
  
          #the stuff below is to order the activity assignments according to input order 
          key_value = [(ans[i], l[i]) for i in range(s)]
  
          fans = ""
          for i in range(s):
              for j in range(s):
                  if enumerated[j][0] == i:
                      fans = fans + key_value[j][0]
  
  
  
          print("Case #" + str(p + 1) + ": " + fans)
  
  </code></pre>