(Chciałem to opublikować, gdy 1542: Konflikt planowania wciąż był bieżącym xkcd, ale miałem konflikt planowania).

Wkład

Dane wejściowe będą listą 3nelementów, które reprezentują nzdarzenia. Pierwszym elementem w każdej grupie 3 będzie nazwa zdarzenia; drugi i trzeci odpowiednio czas rozpoczęcia i zakończenia. Na przykład:

foo 12 34 bar 56 78

reprezentuje zdarzenie, fooktóre zaczyna się od „czasu 12” (czasy są reprezentowane po prostu liczbami całkowitymi; możesz myśleć o nich jako minutach po północy) i kończy się o 34, a drugie zdarzenie, barktóre zaczyna się o 56 i kończy o 78.

Nazwy zdarzeń będą zawsze składać się wyłącznie ze znaków alfanumerycznych, a czasy będą zawsze liczbami całkowitymi ≥ 0 i <1440. Czas zakończenia będzie zawsze o co najmniej 1 większy niż czas rozpoczęcia. Nie gwarantuje się, że zostaną w jakikolwiek sposób posortowane.

Jeśli chcesz, możesz wziąć to jako ciąg oddzielony spacjami; w przeciwnym razie powinien być traktowany jako tablica, lista, wektor lub odpowiednik twojego języka.

Wydajność

Dane wyjściowe powinny być oddzieloną spacjami listą nazw zdarzeń. Reguły, dla których nazwy zdarzeń mają być generowane, są następujące:

• Żadne z generowanych zdarzeń nie może powodować konfliktów. Na przykład, przy wejściu a 0 10 b 5 15, nie może wyjście zarówno aa bponieważ czasy konfliktu (czyli częściowo pokrywają się). Jeśli wydarzenie kończy się dokładnie tak, jak inne, możesz dołączyć oba.

• Nie możesz wyrenderować wydarzenia o nazwie NSCC(„Krajowy konkurs konfliktu planowania”), którego zawsze będzie dokładnie jeden z danych wejściowych. Również koniecznością wyjścia przynajmniej jedno zdarzenie, które konfliktów (częściowo pokrywa się) z NSCC(i zawsze będzie co najmniej jeden z tych, jak również).

• Musisz wygenerować jak najwięcej zdarzeń, przestrzegając dwóch powyższych zasad. (Jest tak, abyś wyglądał na tak zajętego, jak to możliwe, aby pominięcie NSCC wydawało się bardziej wiarygodne).

Może być również wyprowadzany jako pojedynczy ciąg oddzielony spacją lub tablica, lista, wektor itp.

Możliwe jest więcej niż jedno wyjście.

Przypadki testowe

Zauważ, że wymienione dane wyjściowe są tylko przykładami. Twój kod może wyświetlać coś innego, o ile nadal spełnia trzy powyższe reguły (w szczególności oznacza to, że musi być taka sama liczba zdarzeń jak w przykładzie).

W: UnderwaterBasketWeavingConvention 50 800 NSCC 500 550
Out:UnderwaterBasketWeavingConvention

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

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

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

W: 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

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

Możesz dodać więcej przypadków testowych w edycji, jeśli są przypadki, które przegapiłem.

Zasady

• Twój kod musi zostać ukończony w ciągu 30 sekund dla wszystkich dostarczonych przypadków testowych (jest to raczej kontrola poprawności, ponieważ prawdopodobnie powinien zakończyć się znacznie szybciej dla wszystkich przypadków testowych łącznie) na rozsądnej maszynie osobistej.

• To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Pyth, 45 bajtów

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

Ten był trudny do gry w golfa. Znalazłem kilka 45-bajtowych rozwiązań, to jest prawdopodobnie najbardziej egzotyczne, ponieważ używa A(przypisywania par) i .g(grupowania).

Wypróbuj online: Demonstracja lub Uprząż testowa

Wyjaśnienie

                            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 bajtów

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

Krótkie wyjaśnienie tego, co robi każdy predykat:

• z(A,B) sprawdza, czy zdarzenie A nie powoduje konfliktu z żadnym zdarzeniem z listy zdarzeń B
• u(A,B)sprawdza, czy każde zdarzenie z listy A nie powoduje konfliktu z żadnym zdarzeniem z listy B (służy do sprawdzania, czy nie ma konfliktów na liście A przez wywołanie u(A,A))
• y(A,B,C) dzieli listę na listę trojaczków (aby przekształcić dane wejściowe w listę zdarzeń)
• d(A) drukuje nazwy zdarzeń na liście A
• l(A,R) ocenia najdłuższą listę zdarzeń R zawartą na liście list A
• v(A,NSCC,C,R) zwraca listę R zawierającą każdą listę zdarzeń w A, które nie mają wewnętrznego konfliktu i które powodują konflikt ze zdarzeniem NSCC
• s(A,B) true, jeśli B jest podzbiorem A
• x(A) główny predykat, A jest wejściem.

Przypadki testowe : wykonaj test.w tłumaczu po załadowaniu powyższego kodu z dodanymi po nim następującymi:

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

Zajęło mi to znacznie więcej czasu, niż się spodziewałem. Prawdopodobnie można to znacznie pograć w golfa. Prawdopodobnie możesz również użyć różnych bibliotek programowania ograniczeń, aby uzyskać krótsze rozwiązania.

Edycja: Podziękowania dla @Oliphaunt za pomysł użycia A:B:Czamiast [A,B,C]trojaczki. Oszczędza 14 bajtów.

Edit2: Jeszcze raz dziękuję @Oliphaunt za wskazanie, że predykat `` t / 3`` był bezużyteczny. Oszczędza 55 bajtów

Edycja3: Zyskano 11 bajtów przy użyciu gramatyki klauzuli ostatecznej dla predykatów yi d.

JavaScript ( ES6 ), 228

Druga próba, mam nadzieję, że to zadziała.

Moim celem jest najdłuższa sekwencja zdarzeń, w których występuje konflikt synchronizacji, ale brak konfliktu synchronizacji po usunięciu NSCC zdarzenia. Ta zmodyfikowana sekwencja z usuniętym NSCC jest żądanym wyjściem.

Korzystam z funkcji „Pierwsze wyszukiwanie”, badając kolejkę kandydujących rozwiązań, zaczynając od najdłuższego (pierwszy to lista początkowa). Z kandydackiego rozwiązania n zdarzeń buduję i kolejkuję n więcej kandydujących rozwiązań, usuwając jedno ze zdarzeń i zachowując pozostałe.

Rozwiązanie kandydujące jest poprawne, jeśli istnieje konflikt czasowy „taki, jaki jest”, ale po odfiltrowaniu zdarzenia NSCC konflikt nie występuje. Używam podfunkcji K do sprawdzania konfliktów.

Prawdopodobnie można by grać w golfa trochę więcej ...

Przetestuj poniższy fragment kodu (tylko EcmaScript 6, tylko 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 bajtów

Prawdopodobnie jest tam bardziej zwięzła implementacja Java, ale oto moje zadanie:

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 znaków

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]

Tworzy wszystkie możliwe kombinacje i sprawdza każdą z nich.

Test

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

Wydajność:

re
do
mi