Minimum number of platforms required for a railway station

Question

Challenge

Given daily arrival and departure times of every train that reaches a railway station, find the minimum number of platforms required for the railway station so that no train waits.

In other words, find the maximal number of trains simultaneously present in the station.

Input

• a pair of lists of times: arrivals and departures; the two lists have same length; arrival i corresponds to the same train as departure i.
• alternatively, a list of pairs of times, or any equivalent.
• times are numbers between 0, included, and 24, excluded.
• there are no dates, only times: input is the daily schedule and repeats every day.
• the departure time of a train can be lower than its arrival time; in that case, the train is understood to arrive on a day and depart on the next day; that train will require a platform before midnight and after midnight.
• if the arrival time is lower than the departure time, the train is understood to arrive and depart on the same day.
• input can be restricted to integers

Output

• one integer, the minimum required number of platforms.

Test cases

arrivals   = [10, 13, 16]
departures = [12, 15, 18]
out = 1

arrivals   = [10, 11]
departures = [12, 13]
out = 2

arrivals   = [ 1, 3, 7, 9,10,10,19,23]
departures = [11, 4,11,10,11, 2, 2, 2]
out = 5

arrivals   = [1, 2]
departures = [2, 3]
out = 2

arrivals   = [1, 2]
departures = [3, 2]
out = 2

arrivals   = [2, 22]
departures = [5,  6]
out = 2

Rules

• This is code-golf, the shortest code in bytes wins!

Related challenges

• Count the timespans

Answer 1

Jelly, 19 bytes

1ị>×24+)r/€%24ċþF§Ṁ

Try it online!

How it works

If you expand the times out and lay them out as a visual aid you get something like this (3rd test case as an example):

1 2 3 4 5 6 7 8 9 10 11                                       1 2
    3 4     7 8 9 10 11                      19 20 21 22 23 0 1 2
                9 10                                     23 0 1 2 
                  10 11
                  10 11 12 13 14 15 16 17 18 19 20 21 22 23 0 1 2

(Note that the 1 2 in the top right is the continuation into the next day)

From this, it's clear that the number of platforms required is equal to the maximum of the number of repeated occurrences of each time. For example, 10 appears in the ranges 5 times in this example (the maximum), so the output is 5. The only problem is with times spanning multiple days, which we fix by adding 24 to those values.

The code works as follows (out of date):

1ị>×24+)r/€%24ċþF§Ṁ - Main link, takes a list of pairs of times
       )            - Over each pair, map:
1ị                  -   Is the first element...
  >                 -   ...greater than each element?
                    -   This yields [0, 0] for increasing pairs and [0, 1] for decreasing
   ×24              -   Multiply each one by 24
      +             -   Add in to the original pair
                    - This replaces a pair [a, b] with [a, b+24] if b < a
          €         - Over each pair, map:
        r/          -   Convert to a range
           %24      - Modulo all values by 24
                F   - Flatten this list of pairs to get all times a train is at the station
               þ    - Pair each time up with each range, then, over the pairs:
              ċ     - Count how many times the time is in that range (either 1 or 0)
                 §  - Take the sum of all lists, giving the number of times a train is at the station for each time
                  Ṁ - Take the maximum of these sums

Answer 2

Python, 62 bytes

lambda l:max(sum(a-b^b-h^h-a<1for a,b in l)for h in range(24))

Try it online!

Golfing Surculose Sputum's solution. The new part is a-b^b-h^h-a<1 to check whether the time h lies in the interval from a to b taken cyclically, that is, their sorted ordering is a cyclic permutation of [a,h,b]. To do this, we check whether an odd number of the differences a-b, b-h,h-a are negative. I first did this with multiplication (a-b)^(b-h)^(h-a)<1. But, xor (^) lets us do the same and cuts parens with better precedence.

Answer 3

R, 111 bytes

Brute force - unfortunately TIO can't run it but R 4.0.2 on desktop doesn't have stack issues.

{f=pryr::f
`:`=f(a,b,`if`(a<b,a:b,c(a:24,0:b)))
f(a,d,max(sapply(0:24,f(x,sum(mapply(f(u,v,x%in%u:v),a,d))))))}

Try it online!

Much shorter version with simpler logic:

R, 72 bytes

function(a,d)max(sapply(0:24,function(x)sum(a<=x&x<=d|a>d&(x>=a|x<=d))))

Try it online!

Answer 4

Python 2, 73 bytes

lambda l:max(sum([a<=h<=b,not b<h<a][a>b]for a,b in l)for h in range(24))

Try it online!

Input: A list of pairs of time.

For each hour in the day, check how many trains are in the station. Then find the max of those.

Answer 5

05AB1E (legacy), 19 17 bytes

εD¬‹24*+Ÿ24%}˜D¢à

-2 bytes by taking inspiration from the @cairdCoinheringaahing's Jelly answer for the first part (D¬‹24*+), so make sure to upvote him as well.

Input as a list of pairs of times.

Try it online or verify all test cases.

Explanation:

ε             # Map each pair of the (implicit) input-list to:
 D            #  Duplicate the current pair
  ¬           #  Push the first value of the pair (without popping)
   ‹          #  Check for both whether this value is larger (1 if truthy; 0 if falsey)
    24*       #  Multiply both by 24
       +      #  Add it to the pair we duplicated (at the same positions)
        Ÿ     #  Pop the pair and push a list of integers in that inclusive range
         24%  #  Take modulo-24 on each value
}˜            # After the map: flatten the list of lists of integers
  D           # Duplicate the list
   ¢          # Count how many times each value occurs in the list
    à         # Pop and push the maximum
              # (after which it is output implicitly as result)

Uses the legacy version of 05AB1E, where [2,2] with builtin Ÿ would result in [2] (as expected) instead of [2,2].

Answer 6

Jelly, 15 bytes

>/×24+Ṫr%24FĠẈṀ

A monadic Link accepting a list of lists, [arrivals, departures], which yields the number of platforms.

Try it online!

How?

>/×24+Ṫr%24FĠẈṀ - Link: [arrivals, departures] = X
 /              - reduce by
>               -   greater than?
  ×24           - multiply by 24
      Ṫ         - tail (this actually removes the departures from X and yields them,
                        leaving [arivals] as our left argument for the rest of the chain.)
     +          - add (adds 24 to the departures that should be on the next day)
       r        - inclusive range (vectorises)
        %24     - modulo 24 (change to 24 hour times)
           F    - flatten (gets a list of all hours trains are demanding to be at the station)
            Ġ   - group indices by their values
             Ẉ  - length of each (number of trains at the station at each of the utilised hours)
              Ṁ - maximum

---

Also 15 as a dyadic Link accepting arrivals on the left and departures on the right:

>×24+⁹r⁸%24FĠẈṀ

Try it online!

Answer 7

x86-16 machine code, 40 39 bytes

00000000: b217 32db 5156 32f6 ad3a c412 f63a e212  ..2.QV2..:...:..
00000010: f63a d012 f67a 0143 e2ec 3afb 7f02 8afb  .:...z.C..:.....
00000020: 5e59 feca 79dc c3                        ^Y..y..

Listing:

B2 17       MOV  DL, 23             ; loop 23 to 0 hours (h)
        HOUR_LOOP:
32 DB       XOR  BL, BL             ; reset max hour
51          PUSH CX                 ; save array length 
56          PUSH SI                 ; save array pointer 
        TRAIN_LOOP: 
32 F6       XOR  DH, DH             ; clear negatives counter 
AD          LODSW                   ; AL = arrival (a), AH = departure (b) 
3A C4       CMP  AL, AH             ; is a-b negative? 
12 F6       ADC  DH, DH             ; if so, bit-shift 1 into DH 
3A E2       CMP  AH, DL             ; is b-h negative? 
12 F6       ADC  DH, DH             ; if so, bit-shift another 1 
3A D0       CMP  DL, AL             ; is h-a negative? 
12 F6       ADC  DH, DH             ; if so, bit-shift another 1 
7A 01       JP   NOT_AT_STATION     ; was there an odd number of negatives? 
43          INC  BX                 ; if so, increment count of trains at station 
        NOT_AT_STATION: 
E2 EC       LOOP TRAIN_LOOP         ; go to next train 
3A FB       CMP  BH, BL             ; BH = max( BL, BH ) 
7F 02       JG   NOT_MORE           ; if not highest number of trains, continue 
8A FB       MOV  BH, BL             ; BH set to new max 
        NOT_MORE:    
5E          POP  SI                 ; restore array 
59          POP  CX                 ; restore array length 
FE CA       DEC  DL                 ; decrement hour 
79 DC       JNS  HOUR_LOOP          ; if not past zero hour, keep looping 
C3          RET                     ; return to caller

Try it online!

As a callable function. Input array as a list of pairs at SI, length in CX result in BH.

Explanation:

Loops through 24 hours and checks, for each hour, how many trains will be at the station.

Uses @xnor's formula to check cyclical time interval -- that is if a-b, b-h and h-a are an odd number of negative results then h falls within the interval. Each of these are compared and if negative the carry flag (CF) is set and bit-shifted as a 1 or 0 into DH to record the number of negative results.

The parity flag (PF) is then checked, which is set if the number of 1 bits is even. If odd, a counter is incremented for that hour and then compared to the previous highest counter and the max is updated for the result.

Answer 8

APL (Dyalog Extended), 20 bytes (SBCS)

Anonymous tacit infix function taking arrivals as left argument and departures as right argument.

{≢⍉⊢⌸∊⍵}24|⊣…¨⊢+24×>

Try it online!

> 1 if arrival is after departure

24× multiply 24 by that

⊢+ add the right argument (the departure) to that

⊢…¨ inclusive range for each arrival-departure pair

24| division remainder when divided by 24

{…} apply the following lambda (⍵ is the argument, i.e. the list of ranges)

 ∊⍵ ϵnlist (flatten) the argument

 ⊢⌸ table of indices for each unique hour

 ⍉ transpose (so rows, representing how many of each hour there are, become columns)

 ≢ count the number of rows (i.e. the maximum number of occurrences of any hour)

Answer 9

JavaScript (ES6), 75 bytes

Expects a list of pairs of times.

a=>(t=24,g=m=>t--?g(a.map(([a,d])=>n+=(t<a)+(t>d)<=(a>d),n=0)|n<m?m:n):m)``

Try it online!

Answer 10

J, ^{42 35} 33 bytes

[:>./[:+/(([:~:/1#~[,:]+>*[)>:)"0

Try it online!

High level idea:

1. Represent each range with a 0-1 list, one slot for each hour, a 1 meaning that hour is occupied.
2. Sum the rows.
3. Take the max.

Example

Take 1 2 23 f 5 4 2, that is, the ranges:

1 5
2 4
23 2

We apply (([:~:/1#~[,:]+>*[)>:)"0 (mostly J mechanics) to create the 0-1 lists:

0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1

Note how the 23 2 range extends as needed to go into the next day. This is accomplished by ]+>*[ which adds to the right arg ]+ the left arg [ times * "1 if the right arg is less than the let" >.

Next we do the row-wise sum:

0 1 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1

And take the max:

2

Bonus, 34 byte version using Adam's APL approach

[:>./[:#/.~@;([<@-.~&i.1+]+24*>)"0

Try it online!

Answer 11

Charcoal, 24 bytes

Ｆ⮌θＦ⊕﹪⁻⊟ηι²⁴⊞υ⁺ικＩ⌈Ｅυ№υι

Try it online! Link is to verbose version of code. Explanation:

Ｆ⮌θ

Loop through the arrival times in reverse order, as it's easier to process the departure times in reverse order.

Ｆ⊕﹪⁻⊟ηι²⁴

Calculate the time that this train spends at the station...

⊞υ⁺ικ

... and loop over that to push the start, intermediate and end times to the predefined empty list.

Ｉ⌈Ｅυ№υι

For each time in the list, count how many times it appears in the list, and output the maximum of those.

Answer 12

Retina 0.8.2, 117 bytes

\d+
$*11
(1+) (?!\1)
$&24$*
(1+) \1\b
$1
+%`^(1+) 1(1+\1)
$1 $2 1$2
1(1{24})
1
O`1+
(1+)(\s\1\b)*
$#2$*11
O^`\d+
\G\d

Try it online! Takes input as a list of pairs. Explanation:

\d+
$*11

Convert to unary, but increment all of the numbers as Retina has difficulty working with zero.

(1+) (?!\1)
$&24$*

Add 24 to all of the departure times that are less than the arrival times.

(1+) \1\b
$1

If the arrival and departure times are the same then delete one.

+%`^(1+) 1(1+\1)
$1 $2 1$2

Otherwise repeatedly fill in any times in between.

1(1{24})
1

Reduce all of the times "modulo 24" (allowing for the increment).

O`1+

Sort the times.

(1+)(\s\1\b)*
$#2$*11

Count (in unary) the number of occurrences of each times.

O^`\d+

Sort in descending order.

\G\d

Convert the first (i.e. maximum) to decimal.

Answer 13

Arn -fs, 36 34 30 bytes

ö·ògT£nžú#│ä♦PüâTPF™,åé@⁻BFÏc-

Try it!

Explained

Unpacked: :<(({>:}&&[->24 0~:}]:_||=>:}}\):_:@

:<                     Sorted in descending order
  (
    (
      {                Block with key of _
            _          Implied
          >            Is greater than
              _
            :}         Last entry
        &&             Boolean AND
            [          Begin array
                _
              ->       Exclusive range
                24     Literal twenty-four
              0        Literal zero
              ~        1-range
                  _
                :}     
            ]          End sequence
          :_           Flatten
        ||             Boolean OR
            _
          =>           Inclusive range
              _
            :}
      }                End block
      \                Map block over...
        _              ...Variable initialized to STDIN; implied
    )                  End expression
  :_
  :@                   Group based on frequency
)
                       First entry
                       Length

Answer 14

Scala, 113 105 bytes

Saved 8 bytes thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

def f(a:Seq[Int],d:Seq[Int])=(0 to 24).map(x =>(a zip d).count{case(s,e)=>s<=x&x<=e|s>e&(x>=s|x<=e)}).max

Ungolfed version. Try it online!

object Main {
  def platforms(a: Array[Int], d: Array[Int]): Int = {
    (0 to 24).map(x => (a zip d).count { case (start, end) => (start <= x && x <= end) || (start > end && (x >= start || x <= end)) }).max
  }

  def main(args: Array[String]): Unit = {
    println(platforms(Array(10, 13, 16), Array(12, 15, 18)))
    println(platforms(Array(10, 11), Array(12, 13)))
    println(platforms(Array(1, 3, 7, 9, 10, 10, 19, 23), Array(11, 4, 11, 10, 11, 2, 2, 2)))
    println(platforms(Array(1, 2), Array(2, 3)))
    println(platforms(Array(1, 2), Array(3, 2)))
    println(platforms(Array(2, 22), Array(5, 6)))
  }
}