(Ich wollte dies während 1542 posten : Scheduling Conflict war immer noch das aktuelle xkcd, aber ich hatte einen Scheduling-Konflikt.)

Eingang

Die Eingabe ist eine Liste von 3nElementen, die nEreignisse darstellen. Das erste Element in jeder Dreiergruppe ist der Name eines Ereignisses. die zweite und dritte, die Start- und Endzeit. Beispielsweise:

foo 12 34 bar 56 78

stellt ein Ereignis dar foo, das um "Zeit 12" beginnt (Zeiten werden einfach durch ganze Zahlen dargestellt; Sie können sich diese als Minuten nach Mitternacht vorstellen) und endet um 34. Ein zweites Ereignis barbeginnt um 56 und endet um 78.

Die Namen von Ereignissen bestehen immer nur aus alphanumerischen Zeichen und die Zeiten sind immer ganze Zahlen ≥ 0 und <1440. Die Endzeit ist immer mindestens 1 größer als die Startzeit. Es ist nicht garantiert, dass sie in irgendeiner Weise sortiert werden.

Wenn Sie möchten, können Sie dies als einzelne, durch Leerzeichen getrennte Zeichenfolge verwenden. Andernfalls sollte es als Array, Liste, Vektor oder das Äquivalent Ihrer Sprache verwendet werden.

Ausgabe

Die Ausgabe sollte eine durch Leerzeichen getrennte Liste von Ereignisnamen sein. Die Regeln für die Ausgabe von Ereignisnamen lauten wie folgt:

• Keines der von Ihnen ausgegebenen Ereignisse kann zu Konflikten führen. Zum Beispiel mit dem Eingang a 0 10 b 5 15, können Sie nicht ausgegeben beide aund bweil die Zeiten Konflikt (die teilweise Überlappung). Wenn ein Ereignis genau zu Beginn eines anderen Ereignisses endet, können Sie beide einschließen.

• Sie dürfen das genannte Ereignis NSCC("National Scheduling Conflict Competition") nicht ausgeben , von dem es immer genau eines in der Eingabe gibt. Sie müssen auch mindestens ein Ereignis ausgeben, mit dem Konflikte (teilweise Überschneidungen) vorliegenNSCC (und es wird immer mindestens eines davon geben).

• Sie müssen so viele Ereignisse wie möglich ausgeben, während Sie die beiden oben genannten Regeln befolgen. (Dies ist so, dass Sie so beschäftigt wie möglich aussehen, so dass das Fehlen des NSCC glaubwürdiger erscheint.)

Dies kann auch als einzelne durch Leerzeichen getrennte Zeichenfolge oder als Array, Liste, Vektor usw. ausgegeben werden.

Es kann mehr als eine Ausgabe geben.

Testfälle

Beachten Sie, dass die aufgeführten Ausgaben nur Beispiele sind. Ihr Code gibt möglicherweise etwas anderes aus, solange die drei oben genannten Regeln eingehalten werden (dies bedeutet insbesondere, dass dieselbe Anzahl von Ereignissen wie im Beispiel vorhanden sein muss).

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

Fühlen Sie sich frei, weitere Testfälle in einer Bearbeitung hinzuzufügen, wenn es Randfälle gibt, die ich verpasst habe.

Regeln

• Ihr Code muss für alle bereitgestellten Testfälle auf einem vernünftigen PC innerhalb von 30 Sekunden vollständig sein (dies ist eher eine Sicherheitsüberprüfung, da dies für alle Testfälle zusammen wahrscheinlich viel schneller sein sollte).

• Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes.

Pyth, 45 Bytes

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

Dieser war ziemlich schwer zu golfen. Es wurden einige 45-Byte-Lösungen gefunden. Diese ist wahrscheinlich die exotischste, da sie A(Pair-Assign) und .g(Group-By) verwendet.

Probieren Sie es online aus: Vorführ- oder Testgeschirr

Erläuterung

                            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

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,[]),!.

Kurze Erklärung, was jedes Prädikat tut:

• z(A,B) prüft, ob ein Ereignis A mit keinem Ereignis einer Liste von Ereignissen B in Konflikt steht
• u(A,B)überprüft , dass jedes Ereignis einer Liste A nicht Konflikt mit jedem Fall einer Liste B (verwendet um zu überprüfen , dass es keine Konflikte in der Liste A ist durch den Aufruf u(A,A))
• y(A,B,C) Teilt eine Liste in eine Liste von Drillingen (um Eingaben in eine Liste von Ereignissen umzuwandeln)
• d(A) druckt die Namen von Ereignissen in einer Liste A aus
• l(A,R) wertet die längste Liste von Ereignissen R aus, die in der Liste von Listen A enthalten ist
• v(A,NSCC,C,R) gibt eine Liste R zurück, die alle Ereignisse in A enthält, die keinen internen Konflikt haben und mit dem Ereignis NSCC in Konflikt stehen
• s(A,B) true, wenn B eine Teilmenge von A ist
• x(A) Hauptprädikat, A ist die Eingabe.

Testfälle : führen Sie test.im Interpreter aus, nachdem Sie den obigen Code geladen haben, und fügen Sie anschließend Folgendes hinzu:

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]).

Das hat viel mehr Zeit gekostet, als ich erwartet hatte. Damit kann wohl deutlich mehr golfen werden. Sie könnten wahrscheinlich auch die verschiedenen vorhandenen Constraint-Programmierbibliotheken verwenden, um kürzere Lösungen zu erhalten.

Edit: Danke an @Oliphaunt für die Idee, A:B:Canstelle von [A,B,C]Drillingen zu verwenden. Spart 14 Bytes.

Edit2: Nochmals vielen Dank an @Oliphaunt für den Hinweis, dass das Prädikat `` t / 3` nutzlos war. Spart 55 Bytes

Edit3: Erhielt 11 Bytes unter Verwendung der Definitivsatz-Grammatik für Prädikate yund d.

JavaScript ( ES6 ), 228

Zweiter Versuch, ich hoffe dieser funktioniert.

Mein Ziel ist die längste Sequenz von Ereignissen mit einem Zeitkonflikt, aber ohne Zeitkonflikt, wenn das Ereignis NSCC entfernt wird. Diese modifizierte Sequenz mit entferntem NSCC ist die angeforderte Ausgabe.

Ich benutze eine Breitensuche, um eine Reihe von Lösungskandidaten zu untersuchen, beginnend mit der längsten (die erste ist die Anfangsliste). Aus einer Kandidatenlösung von n Ereignissen baue ich n Kandidatenlösungen auf und reihe sie ein, entferne eines der Ereignisse und behalte die anderen.

Eine Kandidatenlösung ist gültig, wenn ein Zeitkonflikt "wie er ist" vorliegt, aber wenn das NSCC-Ereignis herausgefiltert wird, liegt kein Konflikt vor. Ich benutze eine Unterfunktion K, um nach Konflikten zu suchen.

Könnte wohl etwas mehr golfen werden ...

Testen Sie das folgende Snippet (nur EcmaScript 6, FireFox)

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>

Java, 828 Bytes

Es gibt wahrscheinlich eine prägnantere Java-Implementierung, aber hier ist mein 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"};}

Python, 373 Zeichen

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]

Erstellt alle möglichen Kombinationen und überprüft jede.

Prüfung

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

Ausgabe:

D
C
E