Introducción

Usted es supervisor de un estacionamiento y su gerente se está preparando para reducir el tamaño al extremo.

Es una versión simplificada y adaptada de un problema en el nivel superior PAT del año pasado .

Desafío

Se le pide que calcule cuántos automóviles hay en el lote al mismo tiempo, como máximo .

Aplican reglas estándar. Y este es un código de golf, por lo que gana el código más corto.

La primera línea es la cantidad de entradas (no más de 100,000, su entrada puede no contener esta línea si lo desea, ya que es solo una improvisación para determinar dónde termina la entrada ). El siguiente texto contiene una entrada por línea. Y cada entrada incluye tres números:

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

Modificación 2: está bien usar una matriz de triples como entrada.

Modificación 3: puede cambiar el orden de los números en una entrada. Y puedes elegir cuál usar. (ver la sección de Comentarios)

Se garantiza que la entrada sea válida, suponiendo que:

• Car plate numberes un número entero en el rango de 10000~99999
• Timees un número entero en el rango de 0~86400

Y

• Las entradas no están necesariamente ordenadas cronológicamente.
• No hay coche antes del primer segundo.
• No necesariamente hay automóvil después del último segundo.
• Un automóvil no se iría antes de entrar.
• Car plate numberes único. (pero un mismo automóvil puede visitarlo más de una vez)
• Por lo tanto, es imposible que un automóvil ingrese al lote cuando ya está en él.
• Un mismo auto no entraba y salía al mismo tiempo time.
• Se considera que un automóvil está en el lote en el momento de la entrada / salida.

Ejemplo 1

Entrada

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

Salida

3

Explicación

En 16500, coche 12345y 75487estaban en el estacionamiento.

Ejemplo 2

Hice esto porque encontré muchos códigos fallidos en él.

Entrada (con la primera línea omitida)

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

Salida

2

Explicación

En 16500, coche 12345y 75487estaban en el estacionamiento.

Observaciones

En realidad, no se requieren los tres para la salida. Al menos, solo necesita placa + tiempo o entrada / salida + tiempo para el resultado. Pero el algoritmo es ligeramente diferente en dos circunstancias, por lo que la elección de ser más corto permanece desconocida en un idioma determinado. Y, por supuesto, puedes usar los tres números. Entonces los dejo en el desafío.

Mathematica, 33 bytes

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

Tuve que leer la declaración del problema mejor para darme cuenta de que hay un algoritmo mucho más simple que no requiere la información de la placa.

Función sin nombre que devuelve un entero; El formato de entrada es una lista de triples ordenados en el formulario {time, 0|1, license plate}. Comenzamos por Sorting, que hace que la lista sea cronológica y también rompe los lazos de tiempo al ordenar 0s antes que 1s; luego 2#2-1&@@@guarda la información de llegada / salida y olvida el resto, y también convierte 0s en -1s.

Accumulatecalcula los totales acumulados de esa lista; El resultado es una lista de los aspectos negativos de la cantidad de automóviles en el estacionamiento después de cada llegada / salida. Luego Minelige el más pequeño (el más negativo) de estos y el signo negativo se elimina.

Mathematica, 56 bytes

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

La presentación original (los primeros comentarios se refieren a esta presentación). Función sin nombre que devuelve un entero; El formato de entrada es una lista de triples ordenados en el formulario {time, 0|1, license plate}.

La razón por la que elegimos poner la entrada de tiempo primero y la entrada de entrada / salida en segundo lugar es para Sort@#ordenar la lista cronológicamente y registrar las llegadas antes de las salidas si son simultáneas. Después de eso, #3->#2&@@@devuelve una lista de "reglas" del formulario license plate -> 0|1, aún ordenadas cronológicamente.

Luego, FoldList[List,{},...]crea una lista de todos los segmentos iniciales de esa lista de reglas. En realidad, realmente arruina esos segmentos iniciales; el ksegmento inicial termina siendo una lista con una regla en profundidad 2, una regla en profundidad 3, ... y una regla en profundidad k+1. ( FoldList[Append,{},...]produciría el resultado más natural). Sin embargo, <|#|>convierte cada uno de estos segmentos iniciales en una "asociación", que tiene dos efectos deseables: primero, aplana completamente la estructura de la lista anidada que acabamos de crear; y en segundo lugar, obliga a las reglas posteriores a anular las reglas anteriores, que es exactamente lo que necesitamos aquí: para cualquier automóvil que haya abandonado el estacionamiento, el registro de su entrada inicial ya no existe (y de manera similar para los automóviles que vuelven a entrar) .

Entonces, todo lo que queda por hacer es Countcuántos 0s hay en cada una de estas asociaciones, y tomar el Max.

Haskell, 76 63 61 bytes

2 bytes guardados por una variación de la sugerencia de @ nimi.

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

Espera el argumento como una lista de triples en el orden dado por el enunciado del problema.

Para cada tiempo posible (y algo más), buscamos primero los eventos que vienen y luego los que salen del automóvil y los convertimos en una lista de más o menos eventos. Tomamos las sumas parciales de esta lista y luego el máximo de estas sumas parciales.

PHP 7.1, 126117 bytes

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;

toma la entrada del archivo i, ignora la primera línea. Corre con -r.
Requiere una nueva línea final en la entrada. Reemplazar -2con -3para Windows.

Descompostura

# 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 bytes

Un programa completo, lee la entrada de 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);}

Pruébalo con ideone .

Octava, 50 , 64 38 bytes

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

Igual que la respuesta de Mathematica de @Greg Martin

La función obtiene una matriz con 3 columnas. [time, i/o,plateN]

respuesta anterior:

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

¡La función solo obtiene dos entradas t: tiempo y O: E / S del primer elemento de una matriz de celdas Aque contiene entradas triples!

Una matriz dispersa creada para contar para cada número de tiempo registrado de automóviles existentes. Para ello, se considera el tiempo de salida + 1 para la salida del automóvil y el cambio correspondiente de 1 a -1 y 0 cambiado a 1. El
uso de disperso aquí es muy importante ya que varios automóviles pueden llegar o salir al mismo tiempo.
Luego se calcula la suma acumulada que representa el número de automóviles actuales en el lote y el máximo de este.

JavaScript (ES6), 63 73 71 bytes

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

Esto acepta entradas como un conjunto de entradas ordenadas [time, inout, plate]. Desafortunadamente, debido al hecho de que tiempos de salida idénticos significa que ambos autos se consideran en el lote en el momento, el algoritmo de clasificación debe ordenar 0antes 1, lo que costó 11 bytes.

Créditos

• Ahorré 1 byte moviendo completamente el cambio y la multiplicación dentro de la función del mapa (gracias Neil).
• Ahorré otros dos bytes usando un argumento desestructurado en la función de clasificación (gracias edc65).

Manifestación

// 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 bytes

EDITAR: corregido para admitir el segundo ejemplo

Toma datos como una matriz de [in_out, time, plate]matrices. Pero la platecolumna es realmente ignorada.

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

Prueba

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