16
\$\begingroup\$

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.


Santa and the Elves are secretly preparing for a new tourist train service, called "North Pole Railroads". The train will travel through various sightseeing spots near the North Pole.

As a part of this project, they want to know how many seats they will need. They already have the list of travels for each passenger (given as "from station X to station Y"), which is thanks to the same magic that lets Santa know which children are nice. Each station is numbered from 1, starting from the North Pole.

The Elves are arguing over how to determine the number of seats. One option is to absolutely minimize the number of seats needed. Elves will decide which passenger will take which seat. Two passengers with strictly overlapping travel cannot share a seat (e.g. one is (1, 3) and the other is (2, 4)), but a travel that ends at X is not overlapping with another that starts at X.

Task

Given the list of X, Y pairs that represent the travel of each passenger, output how many seats will be needed for North Pole Railroads.

Standard rules apply. The shortest code in bytes wins.

Test cases

(1, 2), (2, 3), (1, 3), (3, 4) -> 2
1---2---3---4
 AAA BBB DDD
 CCCCCCC

(1, 3), (1, 3), (3, 6), (3, 6) -> 2
1...3...6
 AAA CCC
 BBB DDD

(1, 5), (2, 8), (6, 9), (5, 7), (4, 6) -> 3
1...2...3...4...5...6...7...8...9
 AAAAAAAAAAAAAAA DDDDDDD
     BBBBBBBBBBBBBBBBBBBBBBB
             EEEEEEE CCCCCCCCCCC
\$\endgroup\$
6
  • \$\begingroup\$ Am I allowed 0-indexing of station numbers? \$\endgroup\$
    – Neil
    Dec 23, 2022 at 0:23
  • 1
    \$\begingroup\$ @Neil It doesn't matter. The test cases can be interpreted as "there is Station 0, but no one boards there". \$\endgroup\$
    – Bubbler
    Dec 23, 2022 at 0:58
  • 1
    \$\begingroup\$ Can we take input as two lists: starts and ends of the travels? \$\endgroup\$
    – pajonk
    Dec 23, 2022 at 7:14
  • \$\begingroup\$ @pajonk That's fine. \$\endgroup\$
    – Bubbler
    Dec 24, 2022 at 1:29
  • \$\begingroup\$ Can the number of stations that exist be taken (as an additional input)? \$\endgroup\$
    – m90
    Dec 29, 2022 at 10:27

17 Answers 17

7
\$\begingroup\$

Python 3, 48 bytes

lambda a:max(sum(p<x<[q]for*p,q in a)for x in a)

Try it online!


Python 3, 50 bytes

lambda a:max(sum(p<=x<q for p,q in a)for x,y in a)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 48 requires pairs to be lists. \$\endgroup\$ Dec 23, 2022 at 12:24
5
\$\begingroup\$

J, 24 20 bytes

[:>./[:+/1=,.I."#./]

Attempt This Online!

Found independently, but conceptually very similar to tsh's python approach.

  • We find the "insert before" index of every left endpoint within every reversed range
  • This will be 1 iff the left endpoint is contained within the range
  • We sum all the ones for each left endpoint, giving us a count of how many ranges that endpoint is contained in
  • Take the max of all the counts

J, 24 bytes

[:>./[:#/.~@;<@i.@-+&.>]

Try it online!

  • Generates all stops for each person (not including the endpoint), so eg 1 4 becomes 1 2 3.
  • Groups the combined list of all stops by stop, and get a count.
  • Returns the max count.
\$\endgroup\$
5
\$\begingroup\$

R, 40 bytes

\(x,y)max(table(unlist(Map(seq,x,y-1))))

Attempt This Online!

Takes input as two vectors - of starts and ends of the travels.

\$\endgroup\$
5
\$\begingroup\$

Vyxal, 5 bytes

rfĊ↑t

Try it online! Takes a list of start stations and a list of end stations.

r     # range (vectorises)
 f    # flatten
  Ċ   # counts of every element
   ↑  # get the maximum element by its tail
    t # tail

Vyxal, 7 bytes

∩÷rfĊ↑t

Try it online! The original solution, taking a list of pairs. This transposes then item splits ÷ first, before continuing with the solution above.

\$\endgroup\$
4
\$\begingroup\$

Factor, 56 bytes

[ [ last2 [a,b) ] map concat histogram values supremum ]

Try it online!

                    ! { { 1 5 } { 2 8 } { 6 9 } { 5 7 } { 4 6 } }
[ last2 [a,b) ] map ! { { 1 2 3 4 } { 2 3 4 5 6 7 } { 6 7 8 } { 5 6 } { 4 5 } }
concat              ! { 1 2 3 4 2 3 4 5 6 7 6 7 8 5 6 4 5 }
histogram           ! H{ { 1 1 } { 2 2 } { 3 2 } { 4 3 } { 5 3 } { 6 3 } { 7 2 } { 8 1 } }
values              ! { 1 2 2 3 3 3 2 1 }
supremum            ! 3
\$\endgroup\$
4
\$\begingroup\$

Pip, 20 bytes

M:($+:{@_Na,b}MUa)Ma

Try It Online!

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 19 17 15 bytes

I⌈EθΣEθ№…⌊λ⌈λ⌊ι

Try it online! Link is to verbose version of code. Edit: Saved 2 bytes by using Minimum and Maximum to obtain the starting and ending stations for each passenger. Saved a further 2 bytes by only checking the starting stations instead of all stations, which allowed me to rewrite the expression to make it work on TIO as well as ATO. Explanation:

   θ            Input journeys
  E             Map over passengers
      θ         Input journeys
     E          Map over passengers
       №        Count of
             ⌊  Starting station of
              ι Outer passenger in
        …       Range from
         ⌊      Starting station of
          λ     Inner passenger to
           ⌈    Ending station of
            λ   Inner passenger
    Σ           Take the sum
 ⌈              Take the maximum
I               Cast to string
                Implicitly print
\$\endgroup\$
1
  • \$\begingroup\$ I can confirm this is correct. \$\endgroup\$
    – Bubbler
    Dec 23, 2022 at 1:26
4
\$\begingroup\$

Jelly, 7 bytes

‘r"FĠẈṀ

Try it online!

-2 bytes: Takes start stations and end stations as separate lists.

‘r"FĠẈṀ
‘        - increment
 r"      - vectorized range
   F     - flatten
    Ġ    - group indices by value
     Ẉ   - lengths
      Ṁ  - maximum 
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 61 bytes

-3 thanks to @l4m2

a=>a.map(g=([p,q])=>p<q&&g([p+1,q],m+=m<(g[p]=-~g[p])),m=0)|m

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 61 \$\endgroup\$
    – l4m2
    Dec 23, 2022 at 3:30
2
\$\begingroup\$

Python3, 237 bytes:

lambda x:min(f(x))
def f(x):
 q=[(x,[])]
 while q:
  a,b=q.pop(0)
  if[]==a:yield len(b);continue
  for I,i in enumerate(b):
   if all(y<=a[0][0]or a[0][1]<=x for x,y in i):q+=[(a[1:],b[:I]+[[*i,a[0]]]+b[I+1:])]
  q+=[(a[1:],b+[[a[0]]])]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Nibbles, 9 bytes (18 nibbles)

`/.=~+!$_~>$,@$,$]

Takes input as lists of start stations and end stations.

`/.=~+!$_~>$,@$,$]
      !$_           # zip input lists together
         ~          # using function:
          >$        #   drop inp1 elements
            ,@      #   from range 1..inp2
     +              # now flatten the list of lists
   =~               # and group elements
              $     # by their own values;      
  .            ,$   # get the length of each group
`/                  # and fold over this list
                 ]  #   returning the maximum

enter image description here

\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

r/ṖṬ)SṀ

A monadic Link that accepts a list of pairs of station numbers for the passengers and yields the minimum seat count.

Try it online!

How?

r/ṖṬ)SṀ - Link: list of pairs of positive integers, P
    )   - for each (board, alight) in P:
 /      -   reduce by:
r       -     inclusive range -> [board, board+1, ..., alight]
  Ṗ     -   pop (the passenger does not need their seat at their destination)
   Ṭ    -   untruth - e.g. [3,4,5] -> [0,0,1,1,1]
     S  - sum (the columns of that)
      Ṁ - maximum
\$\endgroup\$
1
\$\begingroup\$

Excel (ms365), 111 bytes

enter image description here

Formula in D1:

=MAX(BYROW(A1:B5,LAMBDA(a,LET(x,SEQUENCE(MAX(a)-MIN(a),,MIN(a)+1),MAX(COUNTIFS(A1:A5,"<="&x,B1:B5,">"&x),1)))))
\$\endgroup\$
1
\$\begingroup\$

Haskell, 86 bytes

import Data.Ix
import Data.List
s=maximum.map length.group.sort.concat.map(init.range)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

x86-64 machine code, 33 bytes

92 99 31 C9 57 56 AF 75 02 FF C9 AF 75 02 FF C1 FF CE 75 F2 5E 5F 39 D1 0F 47 D1 FF C8 75 E5 92 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes an array of pairs of 32-bit integers with the address in RDI and the length in ESI, and takes the number of stations in EDI.

This program runs backwards through the stations, keeping track of the number of passengers on the train, and the answer is the highest that number has been.

In assembly:

f:
    xchg edx, eax   # Switch the number of stations into EAX.
    cdq             # Set EDX to 0 by sign-extending EAX.
    xor ecx, ecx    # Set ECX to 0.
            # EAX will hold the current station, ECX the current number of passengers,
            #  and EDX the highest number of passengers so far.
next_station:
    push rdi        # Save the value of RDI onto the stack.
    push rsi        # Save the value of RSI onto the stack.
next_passenger:
    scasd           # Compare EAX and the value at address RDI, advancing the pointer.
    jne s0          # (That value is the starting station.) Jump if they are unequal.
    dec ecx         # (If they are equal) Subtract 1 from the current passenger count.
s0:
    scasd           # Compare EAX and the value at address RDI, advancing the pointer.
    jne s1          # (That value is the ending station.) Jump if they are unequal.
    inc ecx         # (If they are equal) Add 1 to the current passenger count.
s1:
    dec esi         # Subtract 1 from ESI, counting down from the number of passengers.
    jnz next_passenger  # Jump back, to repeat, if it's not zero.
    pop rsi         # Restore the value of RSI from the stack.
    pop rdi         # Restore the value of RDI from the stack.
    cmp ecx, edx    # Compare the current passenger count and EDX.
    cmova edx, ecx  # If the current passenger count is higher, set EDX to that.
    dec eax         # Subtract 1 from EAX, progressing backwards through the stations.
    jnz next_station# Jump back, to repeat, if it's not zero.
    xchg edx, eax   # Switch the highest passenger count into EAX (to be returned).
    ret             # Return.
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 137 134 133 132 bytes

-2 byte thanks to @ceilingcat

m;n;k;i;q;l;main(c,v)int**v;{for(;++n-l;k=0)for(i=1;i++<c;m=fmax(k+=atoi(v[i++-1])<=n&n<q,m))l=fmax(q=atoi(v[i]),l);printf("%d",m);}

Try it online!

\$\endgroup\$
0
0
\$\begingroup\$

05AB1E, 8 bytes

εŸ¨}˜D¢à

Try it online or verify all test cases.

Explanation:

ε      # Map over each pair of the (implicit) input-list:
 Ÿ     #  Pop the pair, and push a list in the inclusive range of it
  ¨    #  Remove the last item (the destination-seat)
}˜     # After the map: flatten the list of lists
  D    # Duplicate it
   ¢   # Pop both, and count how many times each occurs
    à  # Pop and leave the maximum count
       # (which is output implicitly as result)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.