Skip to content

Instantly share code, notes, and snippets.

@ruipgil
Created March 23, 2022 18:00
Show Gist options
  • Save ruipgil/417174f0ee923b32bf7f44af9045eee2 to your computer and use it in GitHub Desktop.
Save ruipgil/417174f0ee923b32bf7f44af9045eee2 to your computer and use it in GitHub Desktop.
defmodule SmallestTimeInterval do
@moduledoc """
Given a list of times in a 24-hour period, return the smallest interval between two times in the list. Hint: you can
do this in O(n) time! Assume the list is unsorted.
Example:
$ smallestTimeInterval(['01:00', '08:15', '11:30', '13:45', '14:10', '20:05'])
$ '25 minutes'
Source: https://buttondown.email/cassidoo/archive/the-best-time-to-make-friends-is-before-you-need/
# Solution
Initialize an array of minutes in a day. Set each given hour to true, count the minimum distance between true's.
Double the array to account for midnight transitions
"""
@init_matrix List.duplicate(false, 60 * 24)
def call(hours) do
hours
|> Enum.reduce(@init_matrix, fn hour, matrix ->
hour
|> hour_to_index()
|> update_matrix(matrix)
end)
|> get_minimum_distance()
|> minutes_to_time()
end
defp hour_to_index(str) do
[hour, minute] = str |> String.split(":") |> Enum.map(&String.to_integer/1)
hour * 60 + minute
end
defp update_matrix(index, matrix), do: List.replace_at(matrix, index, true)
defp get_minimum_distance(matrix) do
# double the matrix to allow for midnight comparisons
(matrix ++ matrix)
|> Enum.reduce(%{candidate: 60000, current: nil}, fn value,
%{candidate: candidate, current: current} ->
case {value, current} do
{false, nil} ->
%{candidate: candidate, current: current}
{false, ^current} ->
%{candidate: candidate, current: (current || 0) + 1}
{true, nil} ->
%{candidate: candidate, current: 1}
{true, ^current} ->
%{candidate: min(current, candidate), current: 1}
end
end)
|> then(fn %{candidate: candidate} -> candidate end)
end
defp minutes_to_time(minutes) do
"#{minutes} minutes"
end
def test() do
call(["23:49", "00:15", "17:30", "18:30"])
|> IO.puts()
end
end
SmallestTimeInterval.test()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment