5
\$\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. Another option is to have just enough seats to allow all passengers to choose their seats. Note that they will have to consider all possible order of reservations. 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) -> 3
1---2---3---4
 AAA     DDD
     BBB
 CCCCCCC
Explanation: if A takes seat 1 and B takes seat 2, C needs the third seat

(1, 2), (1, 3), (2, 3), (3, 4) -> 3
Explanation: the order in the input does not matter

(1, 3), (1, 3), (3, 6), (3, 6) -> 2

(1, 5), (2, 8), (6, 9), (5, 7), (4, 6) -> 5
Explanation: B's travel overlaps with the other 4, so if ACDE gets to book first,
B will need the 5th seat
\$\endgroup\$
8
  • 1
    \$\begingroup\$ In the first test case, why does B get to choose a different seat to A? Surely at that point the train only has one seat. \$\endgroup\$
    – Neil
    Dec 24, 2022 at 9:54
  • \$\begingroup\$ @Neil Because B has the freedom to do so. If B takes the same seat as A, then two seats would be enough, but it is not the worst case. \$\endgroup\$
    – Bubbler
    Dec 25, 2022 at 23:43
  • \$\begingroup\$ Then what's to stop D choosing a different seat from the other three? \$\endgroup\$
    – Neil
    Dec 25, 2022 at 23:53
  • \$\begingroup\$ @Neil ... No, that's not how it works. The train has a fixed number of seats, say N. The task is to find the minimun N that allows everyone to book their seat regardless of order and choice. For the first test case, N=1 clearly doesn't work, and N=2 doesn't either (because A and B may book before C and take two different seats, which is what I explained in the earlier comment). N=3 works, so it is the answer. D's travel simply doesn't contribute to this reasoning (D can book their seat regardless of how A/B/C behave, as long as N >= 1). \$\endgroup\$
    – Bubbler
    Dec 26, 2022 at 0:09
  • 1
    \$\begingroup\$ So N=2 would suffice for the case of (1, 3), (2, 4), (5, 7), (4, 6), but if you include (1, 7) then E can't book if N=2, so you try N=3, but now C can choose seat 3, so you try N=4, but now D can choose seat 4, so you need N=5? \$\endgroup\$
    – Neil
    Dec 26, 2022 at 0:41

5 Answers 5

5
\$\begingroup\$

Jelly, 10 bytes

<>ƭ"Ạ¥þUSṀ

Try it online!

The goal is to find the passenger that whose journey overlaps with the most other passengers. The result is that number +1.

<>ƭ"Ạ¥þUSṀ
      þU    - outer product with itself with reversed elements
<>ƭ"Ạ¥      -   takes [a, b], [c, d] and returns a<c && b>d
        S   - sum rows
         Ṁ  - maximum
\$\endgroup\$
1
\$\begingroup\$

R, 44 bytes

\(a,b)max(rowSums((d=sapply(a,`<`,b))&t(d)))

Attempt This Online!

Same approach as AndrovT (upvote that!), combined with the observation that we can just calculate a single matrix of start-greater-than-stops, and AND it with itself after transposing to get the matrix of all passenger overlaps.
Calculating the matrix is easy in R by taking input as two lists, one of starts and one of stops, and using a vectorized greater-than comparison.

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

JavaScript (Node.js), 60 bytes

x=>Math.max(...x.map(v=>x.map(w=>n+=w.r>v.l&v.r>w.l,n=0)|n))

Try it online!

Same approach as AndrovT

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

Charcoal, 20 bytes

UMθ…⌊ι⌈ιI⌈EθLΦθ⁻ι⁻ιλ

Try it online! Link is to verbose version of code. Explanation: Assumes that @AndrovT's interpretation of the problem is correct.

UMθ…⌊ι⌈ι

Turn each starting and ending pair into a range.

I⌈EθLΦθ⁻ι⁻ιλ

For each passenger, do double set difference to see whether how many ranges intersect with other passengers and output the maximum.

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

Scala, 72 bytes

Modified from @AndrovT's answer


Golfed version, try it online!

def f(t:List[Interval]):Int={t.map{v=>t.count{w=>w.r>v.l&&v.r>w.l}}.max}

Ungolfed version

object Main {
  def main(args: Array[String]): Unit = {
    val intervals = List(Interval(1, 5), Interval(2, 8), Interval(6, 9), Interval(5, 7), Interval(4, 6))
    println(maxOverlap(intervals))
  }

  case class Interval(l: Int, r: Int)

  def maxOverlap(intervals: List[Interval]): Int = {
    intervals.map { v =>
      intervals.count { w =>
        w.r > v.l && v.r > w.l
      }
    }.max
  }
}
\$\endgroup\$

Your Answer

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

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