Wprowadzenie

Jesteś przełożonym parkingu, a twój menedżer przygotowuje się do skrajnego zmniejszenia wielkości.

Jest to uproszczona i dostosowana wersja problemu z zeszłorocznego najwyższego poziomu PAT .

Wyzwanie

Zostaniesz poproszony o obliczenie co najwyżej liczby samochodów na partii .

Obowiązują standardowe zasady. A to jest golf golfowy, więc wygrywa najkrótszy kod.

Pierwszy wiersz to ilość wpisów (nie więcej niż 100,000, twoje wejście może nie zawierać tego wiersza, jeśli chcesz, ponieważ jest to tylko prowizoryczne określenie, gdzie kończy się wejście ). Poniższy tekst zawiera jeden wpis w wierszu. I każdy wpis zawiera trzy liczby:

<Car plate number> <Time (seconds) since open> <0(In) | 1(Out)>

Modyfikacja 2: Można użyć tablicy potrójnych jako danych wejściowych.

Modyfikacja 3: Możesz zmienić kolejność liczb w jednym wpisie. I możesz wybrać, którego użyć. (patrz sekcja Uwagi)

Dane wejściowe są gwarantowane, przy założeniu, że:

• Car plate numberjest liczbą całkowitą z zakresu 10000~99999
• Timejest liczbą całkowitą z zakresu 0~86400

I

• Wpisy niekoniecznie są uporządkowane chronologicznie.
• Przed pierwszą sekundą nie ma samochodu.
• Jest niekoniecznie ma samochodu po ostatniej sekundy.
• Samochód nie chciał odjechać, zanim wsiądzie.
• Car plate numberjest unikalny. (ale ten sam samochód może odwiedzać więcej niż jeden raz)
• Nie ma więc możliwości, aby samochód wjechał na parking, gdy już w nim jest.
• Ten sam samochód nie wsiadałby i wysiadał w tym samym czasie time.
• Uważa się, że samochód znajduje się na partii w momencie wejścia / wyjścia.

Przykład 1

Wejście

11
97845 36000 1
75487 16500 1
12345 16 0
75486 3300 0
12345 6500 1
97845 32800 0
12345 16400 0
97846 16501 1
97846 16500 0
75486 8800 1
75487 3300 0

Wynik

3

Wyjaśnienie

O 16500, samochód 12345i 75487były na parkingu.

Przykład 2

Zrobiłem to, ponieważ znalazłem wiele błędów na nim.

Wejście (z pominięciem pierwszego wiersza)

12345 16400 0
12345 16500 1
75487 16500 0
75487 16600 1

Wynik

2

Wyjaśnienie

O 16500, samochód 12345i 75487były na parkingu.

Uwagi

W rzeczywistości nie wszystkie trzy są wymagane do wydruku. Przynajmniej potrzebujesz tylko płyty + czas lub wejścia / wyjścia + czas na wynik. Ale algorytm jest nieco inny w dwóch okolicznościach, dlatego wybór krótszego czasu pozostaje nieznany w pewnym języku. I oczywiście możesz użyć wszystkich trzech liczb. Zostawiam ich więc wyzwaniu.

Mathematica, 33 bajty

-Min@Accumulate[2#2-1&@@@Sort@#]&

Musiałem lepiej przeczytać instrukcję problemu, aby zdać sobie sprawę, że istnieje znacznie prostszy algorytm, który nie wymaga informacji o tablicach rejestracyjnych.

Nienazwana funkcja zwracająca liczbę całkowitą; format wejściowy to lista uporządkowanych trójek w formularzu {time, 0|1, license plate}. Zaczynamy od Sorting, co sprawia, że ​​lista jest chronologiczna, a także przerywa powiązania czasowe, sortując 0s przed 1s; następnie 2#2-1&@@@przechowuje informacje o przyjeździe / wyjeździe i zapomina resztę, a także konwertuje 0s na -1s.

Accumulateoblicza sumy bieżące tej listy; wynikiem jest lista negatywnych liczb samochodów na parkingu po każdym przyjeździe / wyjeździe. Następnie Minwybiera najmniejszą (najbardziej negatywną) z nich, a znak ujemny jest usuwany.

Mathematica, 56 bajtów

Max[<|#|>~Count~0&/@FoldList[List,{},#3->#2&@@@Sort@#]]&

Oryginalne zgłoszenie (kilka pierwszych komentarzy odnosi się do tego zgłoszenia). Nienazwana funkcja zwracająca liczbę całkowitą; format wejściowy to lista uporządkowanych trójek w formularzu {time, 0|1, license plate}.

Powodem, dla którego wybraliśmy umieszczenie wpisu czasu na pierwszym miejscu, a wpisu wejścia / wyjścia na drugim miejscu, jest to, że Sort@#sortuje listę chronologicznie i rejestruje przyjazdy przed odlotami, jeśli są one jednoczesne. Następnie #3->#2&@@@zwraca listę „reguł” formularza license plate -> 0|1, wciąż posortowanych chronologicznie.

Następnie FoldList[List,{},...]tworzy listę wszystkich początkowych segmentów tej listy reguł. Właściwie to naprawdę psuje te początkowe segmenty; z kth początkowe końce segmentu góry być lista z jednej reguły na głębokości 2, jeden z reguły na głębokości 3, ..., i jedną regułę na głębokości k+1. ( FoldList[Append,{},...]dałby bardziej naturalny wynik). Jednak <|#|>zamienia każdy z tych początkowych segmentów w „skojarzenie”, które ma dwa pożądane efekty: po pierwsze, całkowicie spłaszcza utworzoną właśnie strukturę listy zagnieżdżonej; a po drugie, wymusza późniejsze reguły, aby zastąpić wcześniejsze reguły, czego dokładnie tutaj potrzebujemy - w przypadku każdego samochodu, który opuścił parking, zapis jego pierwszego wjazdu już całkowicie zniknął (i podobnie w przypadku samochodów, które ponownie wjeżdżają) .

Pozostało więc tylko Countustalić, ile 0jest w każdym z tych skojarzeń i wziąć Max.

Haskell, 76 63 61 bajtów

2 bajty zapisane przez odmianę sugestii @ nich.

f l=maximum$scanl1(+)[(-1)^c|i<-[0..8^6],(_,b,c)<-l,i==2*b+c]

Oczekuje argumentu jako listy potrójnych w kolejności podanej w instrukcji problemu.

Dla każdego możliwego czasu (i kilku innych) szukamy najpierw przybycia, a następnie opuszczenia imprez samochodowych i zmieniamy je na listę dodatnich lub ujemnych. Bierzemy częściowe sumy z tej listy, a następnie maksimum tych częściowych sum.

PHP 7.1, 126 117 bajtów

for(;$s=file(i)[++$i];)$d[+substr($s,6)][$s[-2]]++;ksort($d);foreach($d as$a){$r=max($r,$n+=$a[0]);$n-=$a[1];}echo$r;

pobiera dane z pliku i, ignoruje pierwszą linię. Uruchom z -r.
Wymaga wprowadzenia nowego wiersza w danych wejściowych. Wymienić -2z -3Windows.

awaria

# generate 2-dim array; first index=time, second index=0/1 (in/out);
# values=number of cars arriving/leaging; ignore plate number
for(;$s=file(i)[++$i];) # read file line by line (includes trailing newline)
    $d[+substr($s,6)][$s[-2]]++;    # substring to int=>time, last but one character=>1/0
ksort($d);                      # sort array by 1st index (time)
foreach($d as$a)    # loop through array; ignore time
{
    $r=max($r,                      # 2. update maximum count
        $n+=$a[0]                   # 1. add arriving cars to `$n` (current no. of cars)
    );
    $n-=$a[1];                      # 3. remove leaving cars from `$n`
}
echo$r;                         # print result

C, 147 bajtów

Kompletny program odczytuje dane wejściowe z stdin.

int r[86402]={},u,i,n,t;g(s,o){for(;s<86401;n<r[s]?n=r[s]:0,++s)r[s+o]+=o?-1:1;}main(){for(n=0;scanf("%d%d%d",&u,&t,&i)==3;g(t,i));printf("%d",n);}

Wypróbuj na ideone .

Oktawa, 50 , 64 38 bajtów

@(A)-min(cumsum(sortrows(A)(:,2)*2-1))

Taki sam jak odpowiedź Mathematica @Greg Martin

Funkcja otrzymuje tablicę z 3 kolumnami [time, i/o,plateN]

poprzednia odpowiedź:

@(A){[t,O]=A{:};max(cumsum(sparse({++t(!O),t}{2},1,!O*2-1)))}{2}

Funkcja ma tylko dwa wejścia t: czas i O: I / O z pierwszych dwóch elementów tablicy komórkowej, Aktóra zawiera potrójne wejścia!

Rzadka macierz stworzona do liczenia dla każdej zarejestrowanej liczby istniejących samochodów. W tym celu brany jest pod uwagę czas wyjścia + 1 dla wyjścia z samochodu, a odpowiednia 1 zmiana na -1 i 0 zmieniona na 1.
Użycie rzadkiego tutaj jest bardzo ważne, ponieważ wiele samochodów może przyjechać lub odjechać w tym samym czasie.
Następnie obliczana jest skumulowana suma reprezentująca liczbę obecnych samochodów w partii i jej maksimum.

JavaScript (ES6), 63 73 71 bajtów

d=>Math.max(...d.sort((a,[b,c])=>a[s=0]-b||a[1]-c).map(e=>s+=1-e[1]*2))

Akceptuje to dane wejściowe jako tablicę uporządkowanych wpisów [time, inout, plate]. Niestety z uwagi na fakt, że identyczne czasy bezczynności oznaczają, że oba samochody są obecnie rozpatrywane w partii, algorytm sortowania musi zamówić 0wcześniej 1, co kosztowało 11 bajtów.

Kredyty

• Uratowałem 1 bajt, przenosząc przesunięcie i mnożenie wewnątrz funkcji mapy całkowicie (dzięki Neil).
• Zapisałem kolejne dwa bajty, używając zniszczonego argumentu w funkcji sortowania (dzięki edc65).

Próbny

// test the two examples
console.log([[[36000,1],[16500,1],[16,0],[3300,0],[6500,1],[32800,0],[16400,0],[16501,1],[16500,0],[8800,1],[3300,0]],[[16400,0],[16500,1],[16500,0],[16600,1]]].map(
// answer submission
d=>Math.max(...d.sort((a,[b,c])=>a[s=0]-b||a[1]-c).map(e=>s+=1-e[1]*2))
));

JavaScript (ES6), 83 … 68 70 bajtów

EDYCJA: naprawiono, aby obsługiwać 2. przykład

Pobiera dane wejściowe jako tablicę [in_out, time, plate]tablic. Ale platekolumna jest faktycznie ignorowana.

a=>a.sort(([a,b],[c,d])=>b-d||a-c).map(v=>a=(n+=1-v[0]*2)<a?a:n,n=0)|a

Test

let f =

a=>a.sort(([a,b],[c,d])=>b-d||a-c).map(v=>a=(n+=1-v[0]*2)<a?a:n,n=0)|a

console.log(f([
  [1, 36000, 97845],
  [1, 16500, 75487],
  [0, 16,    12345],
  [0, 3300,  75486],
  [1, 6500,  12345],
  [0, 32800, 97845],
  [0, 16400, 12345],
  [1, 16501, 97846],
  [0, 16500, 97846],
  [1, 8800,  75486],
  [0, 3300,  75487]
]));

console.log(f([
  [0, 16400, 12345],
  [1, 16500, 12345],
  [0, 16500, 75487],
  [1, 16600, 75487]
]));