National Scheduling Conflict Championships

Question

(I meant to post this while 1542: Scheduling Conflict was still the current xkcd, but I had a scheduling conflict.)

Input

The input will be a list of 3n elements, which represent n events. The first element in each group of 3 will be the name of an event; the second and third, the start and end time respectively. For example:

foo 12 34 bar 56 78

represents an event foo that starts at "time 12" (times are represented simply by integers; you can think of them as minutes past midnight) and ends at 34, and a second event bar that starts at 56 and ends at 78.

The names of events will always consist of only alphanumeric characters, and the times will always be integers ≥ 0 and < 1440. The end time will always be at least 1 greater than the start time. They are not guaranteed to be sorted in any way.

If you would like, you may take this as a single space-separated string; otherwise it should be taken as an array, list, vector, or your language's equivalent.

Output

The output should be a space-separated list of event names. The rules for which event names to output are as follows:

• None of the events that you output may conflict with each other. For example, with the input a 0 10 b 5 15, you may not output both a and b because the times conflict (that is, partially overlap). If an event ends exactly as another one starts, you may include both.

• You may not output the event called NSCC ("National Scheduling Conflict Competition"), of which there will always be exactly one of in the input. You also must output at least one event that conflicts (partially overlaps) with NSCC (and there will always be at least one of those as well).

• You must output as many events as possible while following the above two rules. (This is so that you look as busy as possible, so that missing the NSCC seems more credible.)

This may also be output as either a single space-separated string or an array, list, vector, etc.

There can be more than one possible output.

Test cases

Note that the outputs listed are only examples. Your code may output something different, as long as it still follows the three rules above (notably, this means there must be the same amount of events as the example).

In: UnderwaterBasketWeavingConvention 50 800 NSCC 500 550
Out: UnderwaterBasketWeavingConvention

In: SconeEating 0 50 RegexSubbing 45 110 CodeGolfing 95 105 NSCC 100 200
Out: SconeEating CodeGolfing

In: VelociraptorHunting 0 300 NerdSniping 200 500 SEChatting 400 700 DoorknobTurning 650 750 NSCC 725 775
Out: NerdSniping DoorknobTurning

In: NSCC 110 115 A 100 120 B 120 140 C 105 135 D 100 105 E 135 500
Out: C D E

In: A 800 900 NSCC 700 1000 B 650 750 C 950 1050 D 655 660 E 660 665 F 1030 1040 G 1040 1060
Out: A D E F G

In: A 10 11 B 11 12 C 12 13 D 13 14 NSCC 15 1090 E 10 16
Out: E

Feel free to add more test cases in an edit if there are edge-cases that I missed.

Rules

• Your code must complete within 30 seconds for all of the provided test cases (this is more of a sanity check, as it should probably complete much faster for all the test cases combined) on a reasonable personal machine.

• This is code-golf, so the shortest code in bytes wins.

Answer 1

SWI-Prolog, 537 524 516 502 447 436 bytes

z(A:B:C,[D:E:F|G]):-(A=D;B>=F;E>=C),(G=[];z(A:B:C,G)).
u([A|B],C):-z(A,C),(B=[];u(B,C)).
y([A,B,C|D])-->[A:B:C],(y(D);{_=_}).
d-->[A:_],{write(A),tab(1)},d;{_=_}.
l([H|T],R):-T=[],R=H;length(H,N),l(T,X),length(X,M),(N>M,R=H;R=X).
v([],_,R,R).
v([A|T],Z,B,R):-u(A,A),\+z(Z,A),v(T,Z,[A|B],R);v(T,Z,B,R).
s([E|T],[F|N]):-E=F,(N=[];s(T,N));s(T,[F|N]).
x(A):-y(A,D,[]),K="NSCC":_,select(K,D,E),setof(L,s(E,L),B),v(B,K,[],R),l(R,S),d(S,[]),!.

Brief explanation of what each predicate does:

• z(A,B) checks that an event A doesn't conflict with any event of a list of events B
• u(A,B) checks that every event of a list A does not conflict with any event of a list B (used to check that there are no conflicts in list A by calling u(A,A))
• y(A,B,C) splits a List into a list of triplets (to transform inputs into a list of events)
• d(A) prints the names of events in a list A
• l(A,R) evaluates the longest list of events R contained in the list of lists A
• v(A,NSCC,C,R) returns a list R containing every list of events in A that have no internal conflict and that conflict with the event NSCC
• s(A,B) true if B is a subset of A
• x(A) main predicate, A is the input.

Test cases: execute test. in the interpreter after loading the code above with the following added after it:

test:-
    x(["UnderwaterBasketWeavingConvention",50,800,"NSCC",500,550]),
    nl,
    x(["SconeEating",0,50,"RegexSubbing",45,110,"CodeGolfing",95,105,"NSCC",100,200]),
    nl,
    x(["VelociraptorHunting",0,300,"NerdSniping",200,500,"SEChatting",400,700,"DoorknobTurning",650,750,"NSCC",725,775]),
    nl,
    x(["NSCC",110,115,"A",100,120,"B",120,140,"C",105,135,"D",100,105,"E",135,500]),
    nl,
    x(["A",800,900,"NSCC",700,1000,"B",650,750,"C",950,1050,"D",655,660,"E",660,665,"F",1030,1040,"G",1040,1060]),
    nl,
    x(["A",10,11,"B",11,12,"C",12,13,"D",13,14,"NSCC",15,1090,"E",10,16]).

This took me way more time than I thought it would. This can probably be golfed significantly more. Also you could probably use the various constraint programming libraries that exist to get shorter solutions.

Edit: Thanks to @Oliphaunt for the idea of using A:B:C instead of [A,B,C] for triplets. Saves 14 bytes.

Edit2: Thanks again to @Oliphaunt for pointing out that the predicate ``t/3`was useless. Saves 55 bytes

Edit3: Gained 11 bytes using definitive clause grammar on predicates y and d.

Answer 2

Pyth, 45 bytes

AGH.gqhk"NSCC"m,hdrFtdcQ3hMef&.{KseMT@KehHtyG

This one was quite tough to golf. Found quite a few 45 byte solutions, this one is probably the most exotic one, since it uses A (pair-assign) and .g (group-by).

Try it online: Demonstration or Test harness

Explanation

                            implicit: Q = input list
                      cQ3   split Q into triples
              m             map each triple d to:
               ,              the pair containing
                hd              - d[0] (name)
                  rFtd          - range from start-time to end-time
   .g                       group these tuples k by:
     qhk"NSCC"                k[0] == "NSCC"
AGH                         pair assign to G,H. This assigns all
                            tuples != NSCC to G, and the NSCC one to H

                  yG        generate all subsets of G
                 t          remove the first one (the empty subset)
   f                        filter for subsets T, which satisfy:
         eMT                  get the last item (the range) for all tuples in T
        s                     and combine them (sum)
       K                      assign to K
     .{                       check for uniqueness of K (no overlapping times)
    &                         and
            @KehH             check the intersection of K and H[0][1]
  e                         take the last element (most events)
hM                          get the first item (name) for each event
                            and implicitly print this list

Answer 3

JavaScript (ES6), 228

Second try, I hope this one works.

My target is the longest sequence of events that has a timing conflict, but no timing conflict when the event NSCC is removed. This modified sequence with NSCC removed is the output requested.

I use a Breadth First Search examining a queue of candidate solutions, starting with longest (the first is the initial list). From a candidate solution of n events I build and enqueue n more candidate solutions, removing one of the events and keeping the others.

A candidate solution is valid if there is a timing conflict 'as is', but when the NSCC event is filtered out there is no conflict. I use a subfunction K to check for conflicts.

Probably could be golfed a little more...

Test running the snippet below (being EcmaScript 6, FireFox only)

F=l=>(K=>{
  l.map(v=>l.push(l.splice(0,3)));// I'm particularly proud of this trick for grouping in triplets (in pith it's "cQ3")
  for(S=[l.sort((a,b)=>a[1]-b[1])];!K(l=S.shift())|K(m=l.filter(x=>x[0]!='NSCC'));)
    l.map((v,i)=>(S.push(n=[...l]),n.splice(i,1)));
})(l=>l.some(x=>[p>+x[1],p=+x[2]][0],p=0))||m.map(x=>x[0])

// Less golfed and ES5

function Find(l) {
  var n,m;
  var Check = function(l) {
    // check timing conflict comparing start time and end time of previous event (events must be sorted)
    var p = 0 // previous event end time, init to 0
    return l.some( function(x) {
      var err = p > +x[1]; // unary plus convert string to number
      p = +x[2]; // update end time
      return err;
    });  
  };  
  // group initial array in triplets
  // forEach repeats for the initial number of elements in l, even if l becomes shorter
  // so it loops more times than necesary, but it works anymay
  l.forEach(function() { 
    l.push(l.splice(0,3)); // remove first 3 elements and add to back as a triple
  }) 
  l.sort(function(a,b) { return a[1]-b[1]} ); // sort by start time
  var S=[l]; // S is the main queue, start with complete list 
  
  while (l = S.shift(), // current list
         m = l.filter( function(x) { return x[0]!='NSCC'} ), // current list with NSCC removed
         !Check(l)|Check(m)) // loop while list ha no errors or filtered list do have errors
  {
    // build new candidate to check
    l.forEach ( function(v,i) {
      n = l.slice(); // make a copy of l
      n.splice(i,1); // remove ith element
      S.push(n); // put in S
    });  
  }
  // when exiting while, m has the list with NSCC removed
  return m.map( function(x) { return x[0]; }); // keep the event name only
}

// Test

out=(...x)=>O.innerHTML += x + '\n';

test=[
  ['UnderwaterBasketWeavingConvention 50 800 NSCC 500 550','UnderwaterBasketWeavingConvention']
, ['SconeEating 0 50 RegexSubbing 45 110 CodeGolfing  95 105 NSCC 100 200','SconeEating CodeGolfing']
, ['VelociraptorHunting 0 300 NerdSniping 200 500 SEChatting 400 700 DoorknobTurning 650 750 NSCC 725 775'
  ,'NerdSniping DoorknobTurning']
, ['NSCC 110 115 A 100 120 B 120 140 C 105 135 D 100 105 E 135 500','C D E']
, ['A 800 900 NSCC 700 1000 B 650 750 C 950 1050 D 655 660 E 660 665 F 1030 1040 G 1040 1060','A D E F G']
, ['A 10 11 B 11 12 C 12 13 D 13 14 NSCC 15 1090 E 10 16','E']
]


test.forEach(x=>{
  var l=x[0].split(/\s+/), r=F(l).sort().join(' '), e=x[1].split(/\s+/).sort().join(' ');
  out('Test ' + (r==e ? 'OK':'FAIL')+'\nInput:    '+x[0]+'\nResult:   '+r+'\nExpected: '+e)
} )

<pre id=O></pre>

Answer 4

Java, 828 bytes

There's probably a more concise Java implementation out there, but here's my stab:

String s(String e){String[] a=e.split(" ");String m="";String[] c=g(a.length/3);int l=0;for(int i=0;i<a.length;i+=3)if(a[i].equals("NSCC"))l=i/3;for(String p:c)if(p.indexOf(l+"")==-1&&!h(p,a)&&h(p+l,a)&&p.length()>m.length())m=p;String r="";for(int i=0;i<m.length();i++)r+=a[3*(m.charAt(i)-48)]+((i==m.length()-1)?"":" ");return r;}boolean h(String c, String[] e){for(int i=0;i<c.length()-1;i++){int p=c.charAt(i)-48;for(int j=i+1;j<c.length();j++){int q=c.charAt(j)-48;if((Integer.parseInt(e[3*p+1])-Integer.parseInt(e[3*q+2]))*((Integer.parseInt(e[3*p+2])-Integer.parseInt(e[3*q+1])))<0)return true;}}return false;}String[] g(int n){if(n>1){String[] result=new String[(int)Math.pow(2,n)];String[] l=g(n-1);for(int i=0;i<l.length;i++){result[2*i]=l[i];result[2*i+1]=l[i]+(n-1);}return result;}else return new String[]{"","0"};}

Answer 5

Python, 373 characters

import itertools as j
a=zip(*[iter(input())]*3)
f,g,r=[],0,"NSCC"
p=f
for q in a:
 p=(p,q)[q[0]==r]
for h in range(1,len(a)+1):
 for i in j.combinations(a,h):
  s,i,l,m=0,sorted(i,key=lambda k:int(k[1])),-1,len(i)
  for n in i:
   s=(s,1)[p[1]<n[2]or p[2]<n[1]]
   if r==n[0]or n[1]<l:
    m=-1
    break
   else:
    l=n[2]
  if s*m>g:
   g,f=m,i
for o in f:
 print o[0]

Creates all possible combinations and checks each one.

Test

Input: ["NSCC",110,115,"A",100,120,"B",120,140,"C",105,135,"D",100,105,"E",135,500]

Output:

D
C
E