기차역에 필요한 최소 플랫폼 수
도전
기차역에 도착하는 모든 열차의 매일 도착 및 출발 시간을 감안할 때 기차가 기다리지 않도록 기차역에 필요한 최소 플랫폼 수를 찾으십시오.
즉, 역에 동시에 존재하는 최대 열차 수를 찾으십시오.
입력
- 한 쌍의 시간 목록 : 도착 및 출발; 두 목록의 길이는 같습니다. 도착
i은 출발과 동일한 열차에 해당합니다i. - 대안 적으로 , 시간의 쌍, 또는 임의의 등가의리스트.
- 시간은
0, 포함 및24제외 사이의 숫자 입니다. - 날짜는없고 시간 만 : 입력은 일일 일정이며 매일 반복됩니다.
- 기차의 출발 시간은 도착 시간보다 낮을 수 있습니다. 이 경우 기차는 하루에 도착하고 다음날 출발하는 것으로 이해됩니다. 그 기차는 자정 이전과 자정 이후에 플랫폼이 필요합니다.
- 도착 시간이 출발 시간보다 낮을 경우 열차는 당일 도착 및 출발하는 것으로 이해됩니다.
- 입력은 정수로 제한 될 수 있습니다.
산출
- 하나의 정수, 필요한 최소 플랫폼 수입니다.
테스트 케이스
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
규칙
- 이것은 코드 골프입니다. 바이트 단위의 가장 짧은 코드가 이깁니다!
관련 과제
- 기간 계산
답변
Python , 62 바이트
lambda l:max(sum(a-b^b-h^h-a<1for a,b in l)for h in range(24))
온라인으로 시도하십시오!
Golfing Surculose Sputum의 솔루션 . 새로운 부분은 a-b^b-h^h-a<1시간이 주기적 으로 취해지는 h간격에 있는지 , 즉 정렬 된 순서가의 순환 순열인지 확인하는 것입니다 . 이를 위해, 우리는 차이 홀수 여부를 확인 , , 음. 저는 먼저 곱셈으로 이것을했습니다 . 그러나 xor ( )를 사용하면 동일한 작업을 수행하고 더 나은 우선 순위로 괄호를 자릅니다.ab[a,h,b]a-bb-hh-a(a-b)^(b-h)^(h-a)<1^
젤리 , 19 바이트
1ị>×24+)r/€%24ċþF§Ṁ
온라인으로 시도하십시오!
작동 원리
타임 아웃을 확장하고 시각 자료로 배치하면 다음과 같은 결과를 얻을 수 있습니다 (예 : 세 번째 테스트 사례).
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
( 1 2오른쪽 상단의 표시는 다음 날로 이어짐)
이로부터 필요한 플랫폼 수가 매번 반복되는 최대 횟수와 동일하다는 것이 분명합니다. 예를 들어,이 예에서는 범위에 10이 5 번 나타나므로 (최대 값) 출력은 5입니다. 유일한 문제는 여러 날에 걸친 시간에 대한 것입니다.이 값에 24를 더하여 수정합니다.
코드는 다음과 같이 작동합니다 (오래됨).
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
Python 2 , 73 바이트
lambda l:max(sum([a<=h<=b,not b<h<a][a>b]for a,b in l)for h in range(24))
온라인으로 시도하십시오!
입력 : 시간 쌍 목록입니다.
하루 중 한 시간마다 역에 몇 대의 기차가 있는지 확인하십시오. 그런 다음 그 최대 값을 찾으십시오.
R , 111 바이트
Brute force-안타깝게도 TIO는 실행할 수 없지만 데스크톱의 R 4.0.2에는 스택 문제가 없습니다.
{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))))))}
온라인으로 시도하십시오!
더 간단한 논리를 가진 훨씬 더 짧은 버전 :
R , 72 바이트
function(a,d)max(sapply(0:24,function(x)sum(a<=x&x<=d|a>d&(x>=a|x<=d))))
온라인으로 시도하십시오!
APL (Dyalog Extended) , 20 바이트 ( SBCS )
도착을 왼쪽 인수로, 출발을 오른쪽 인수로 취하는 익명의 암묵 중위 함수.
{≢⍉⊢⌸∊⍵}24|⊣…¨⊢+24×>
온라인으로 시도하십시오!
> 도착이 출발 후인 경우 1
24× 그것으로 24를 곱하십시오
⊢+ 그것에 올바른 인수 (출발)를 추가하십시오.
…¨ 각 도착-출발 쌍에 대한 포함 범위
24| 24로 나눈 경우 나눗셈 나머지
{… } 다음 람다를 적용합니다 ( ⍵인수, 즉 범위 목록).
∊⍵ ϵ nlist (평탄화) 인수
⊢⌸ 각 고유 시간에 대한 인덱스 테이블
⍉ 전치 (따라서 각 시간의 수를 나타내는 행이 열이 됨)
≢ 행 수를 계산합니다 (즉, 한 시간의 최대 발생 횟수).
05AB1E (레거시) , 19 17 바이트
εD¬‹24*+Ÿ24%}˜D¢à
-2 바이트는 @cairdCoinheringaahing 의 첫 번째 부분 ( D¬‹24*+)에 대한 Jelly 답변 에서 영감을 얻었 으므로 그 에게도 찬성 투표 를해야합니다.
시간 쌍 목록으로 입력합니다.
온라인으로 시도 하거나 모든 테스트 사례를 확인하십시오 .
설명:
ε # 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)
05AB1E의 레거시 버전을 사용합니다. 여기서 [2,2]builtin Ÿ을 [2]사용하면 [2,2].
젤리 , 15 바이트
>/×24+Ṫr%24FĠẈṀ
[arrivals, departures]플랫폼 수를 산출 하는 목록 목록을 허용하는 모나 딕 링크 .
온라인으로 시도하십시오!
어떻게?
>/×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
또한 arrivals왼쪽과 departures오른쪽에 허용되는 이중 링크로 15 :
>×24+⁹r⁸%24FĠẈṀ
온라인으로 시도하십시오!
x86-16 기계 코드, 40 39 바이트
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..
목록 :
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
온라인으로 시도하십시오!
호출 가능한 함수로. (A)에서 쌍리스트로서 입력 어레이 SI의 길이 CX에 따라서 BH.
설명:
24 시간을 순환하며 각 시간마다 역에 몇 대의 기차가 있는지 확인합니다.
@xnor의 공식 을 사용 하여 주기적 시간 간격을 확인합니다. 즉 a-b, b-h이고 h-a음수 결과가 홀수이면 h해당 간격 내에 속합니다. 이들 각각을 비교하고 음수이면 캐리 플래그 ( CF)가 설정되고 음수 결과 수를 기록하기 위해 1또는 0로 비트 시프트됩니다 DH.
그런 다음 패리티 플래그 ( PF)가 확인되며 1비트 수가 짝수 이면 설정됩니다 . 홀수 인 경우 해당 시간 동안 카운터가 증가한 다음 이전 최고 카운터와 비교되고 결과에 대해 최대 값이 업데이트됩니다.
JavaScript (ES6), 75 바이트
시간 쌍 목록이 필요합니다.
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)``
온라인으로 시도하십시오!
J , 42 35 33 바이트
[:>./[:+/(([:~:/1#~[,:]+>*[)>:)"0
온라인으로 시도하십시오!
높은 수준의 아이디어 :
- 각 범위를 0-1 목록 (시간당 하나의 슬롯)으로 표시합니다.
1이는 시간이 사용됨을 의미합니다. - 행을 합산하십시오.
- 최대를 취하십시오.
예
1 2 23 f 5 4 2즉, 범위를 취하십시오 .
1 5
2 4
23 2
(([:~:/1#~[,:]+>*[)>:)"00-1 목록을 만들기 위해 (대부분 J 역학)을 적용 합니다.
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
23 2다음 날로 이동하기 위해 필요에 따라 범위가 어떻게 확장 되는지 확인하십시오 . 이것은에 의해 달성된다 ]+>*[인수 오른쪽에 추가되는 ]+왼쪽 인수의 [시간 *"올바른 인수 덜하자 이상의 경우 1" >.
다음으로 행별 합계를 수행합니다.
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
그리고 최대를 얻으십시오.
2
보너스, Adam의 APL 접근 방식을 사용하는 34 바이트 버전
[:>./[:#/.~@;([<@-.~&i.1+]+24*>)"0
온라인으로 시도하십시오!
Arn -fs , 36 34 30 바이트
ö·ògT£nžú#│ä♦PüâTPF™,åé@⁻BFÏc-
시도 해봐!
설명
포장 풀기 : :<(({>:}&&[->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
차콜 , 24 바이트
Ｆ⮌θＦ⊕﹪⁻⊟ηι²⁴⊞υ⁺ικＩ⌈Ｅυ№υι
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 설명:
Ｆ⮌θ
출발 시간을 역순으로 처리하는 것이 더 쉽기 때문에 도착 시간을 역순으로 반복합니다.
Ｆ⊕﹪⁻⊟ηι²⁴
이 기차가 역에서 보내는 시간을 계산하세요 ...
⊞υ⁺ικ
...이를 반복하여 시작, 중간 및 종료 시간을 미리 정의 된 빈 목록으로 푸시합니다.
Ｉ⌈Ｅυ№υι
목록에 표시 될 때마다 목록에 표시되는 횟수를 세고 최대 값을 출력합니다.
Retina 0.8.2 , 117 바이트
\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
온라인으로 시도하십시오! 쌍의 목록으로 입력을받습니다. 설명:
\d+
$*11
단항으로 변환하지만 Retina는 0으로 작업하는 데 어려움이 있으므로 모든 숫자를 증가시킵니다.
(1+) (?!\1)
$&24$*
도착 시간보다 짧은 모든 출발 시간에 24를 더합니다.
(1+) \1\b
$1
도착 시간과 출발 시간이 같으면 하나를 삭제하십시오.
+%`^(1+) 1(1+\1)
$1 $2 1$2
그렇지 않으면 중간에 아무 때나 반복해서 입력하십시오.
1(1{24})
1
모든 시간을 "모듈로 24"로 줄입니다 (증가 허용).
O`1+
시간을 정렬하십시오.
(1+)(\s\1\b)*
$#2$*11
각 시간의 발생 수를 (단항으로) 계산합니다.
O^`\d+
내림차순으로 정렬합니다.
\G\d
첫 번째 (즉, 최대 값)를 십진수로 변환합니다.