9
\$\begingroup\$

This challenge was greatly inspired by this Stack Overflow post.

Challenge

Given a bunch of clients in terms of when they enter a room and when they exit it, determine the period(s) of time when the room has a maximum number of people. The time resolution should be to the minute.

For example, if there are three clients 8 - 10, 9 - 11, 10 - 12, then the correct answer would be 9 - 11; during this time period, there are two clients in the room, which is the largest possible.

Input

Input will be a list of pairs in some form. That can be either a list of 2-tuples, an even-length list with elements interleaved, etc, any reasonable input format. The times can be given in any reasonable format, in either 12- or 24- hour time. You may also input time as the number of minutes past midnight.

Output

Output should be a list of pairs in some form, but the output is stricter. The output cannot be a flat list, it must be a list of 2-tuples or a list of lists, etc. The times can be output in any reasonable format, in either 12- or 24- hour time. You may also output time as the number of minutes past midnight.

Examples

input
output

INPUT
08:00 - 10:00
09:00 - 11:00
10:00 - 12:00
OUTPUT
09:00 - 11:00

INPUT
08:20 - 09:20
09:00 - 09:10
08:00 - 09:30
08:50 - 10:40
OUTPUT
09:00 - 09:10

INPUT
08:00 - 10:00
09:00 - 10:00
09:30 - 11:00
OUTPUT
09:30 - 10:00 # The output is not always in the input list

INPUT
00:00 - 02:00
01:00 - 03:00
04:00 - 06:00
05:00 - 07:00
OUTPUT # This is the expected output for when there are multiple time ranges with the same "business".
01:00 - 02:00
05:00 - 06:00

You may assume that the second time in a pair will always be after the first time. Time ranges will not run over midnight.

\$\endgroup\$
  • \$\begingroup\$ What if there are multiple time ranges? \$\endgroup\$ – Esolanging Fruit May 7 '17 at 12:26
  • \$\begingroup\$ @Challenger5 What do you mean by multiple time ranges, Input or output? \$\endgroup\$ – HyperNeutrino May 7 '17 at 12:27
  • \$\begingroup\$ @HyperNeutrino Output. \$\endgroup\$ – Esolanging Fruit May 7 '17 at 12:30
  • \$\begingroup\$ @Challenger5 Added a test case, thanks. \$\endgroup\$ – HyperNeutrino May 7 '17 at 12:31
  • \$\begingroup\$ Is 09:00 - 10:00, 10:00 - 11:00 a valid output for the first test case? \$\endgroup\$ – Leaky Nun May 7 '17 at 12:34
4
\$\begingroup\$

Brachylog, 25 bytes

⟦₂ᵐkᵐcoḅlᵒlᵍthᵐ~c{~k~⟦₂}ᵐ

Try it online!

There's an obvious structure to this answer, which becomes even more obvious if you write it like this:

{⟦₂k}ᵐc oḅ lᵒlᵍ thᵐ ~c{~k~⟦₂}ᵐ

Unfortunately, Brachylog's evaluation order makes it so that the program goes into an infinite loop if you try to take advantage of the structure in question. Still, it's certainly possible to imagine a Brachylog-like language in which this is much shorter.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 22 21 20 bytes

r/€Ṗ€F©®ċ$ÐṀQœ^‘$Ṣs2

Try it online!

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

Brachylog, 58 bytes

⟦₂ᵐkᵐcoḅBlᵐ⌉;B↔z{hl~t?}ˢhᵐhᵐ{∋+₁.¬∈?∧|∋.-₁¬∈?∧}ᶠo~c.{l2}ᵐ∧

Try it online!

This has to be the longest Brachylog answer ever...

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

Pyth, 33 24 bytes

JsrMQcSs-M_BhMBS{.M/JZJ2

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This appears to behave incorrectly for this. I will add this as a test case into the question as well. \$\endgroup\$ – HyperNeutrino May 7 '17 at 12:29
  • \$\begingroup\$ @HyperNeutrino fixed. \$\endgroup\$ – Leaky Nun May 7 '17 at 12:31
  • \$\begingroup\$ Well, that was a fast answer. Nice job! \$\endgroup\$ – HyperNeutrino May 7 '17 at 12:31
0
\$\begingroup\$

Mathematica, 104 bytes

Reduce[#==#~MaxValue~x,x]&@PiecewiseExpand@Tr[Piecewise@{{1,#<=x<#2}}&@@@#]/.{Or->List,a_<=x<b_->{a,b}}&

Of course, this assumes that several high-power Mathematica built-ins are correct...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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