Skip to content

Instantly share code, notes, and snippets.

@delneg
Created January 9, 2022 20:07
Show Gist options
  • Save delneg/45741ec680863483179aebd5a7b470b9 to your computer and use it in GitHub Desktop.
Save delneg/45741ec680863483179aebd5a7b470b9 to your computer and use it in GitHub Desktop.
Intervals merge problem in F#, run with `dotnet fsi intervals.fsx`
//Run with `dotnet fsi intervals.fsx`
let intervals = [|
(1,3)
(12,15)
(23, 41)
(8,10)
(2,6)
(13,21)
(20,21)
(14,22)
|]
let output = [|
(1,6)
(8,10)
(12,22)
(23,41)
|]
let overlaps (int1:int*int) (int2:int*int) :bool =
fst int1 >= fst int2 && fst int1 <= snd int2
let mergeIntervals iis =
if (iis |> Array.length) = 1 then
iis
else
let sortedInput = Array.sortBy (fst) iis
let result = ResizeArray(capacity=iis.Length)
result.Add(iis[0])
for i in 1..sortedInput.Length-1 do
let current = sortedInput[i]
let lastInterval = result |> Seq.last
if overlaps current lastInterval then
result[result.Count - 1] <- (
min (fst current) (fst lastInterval),
max (snd current) (snd lastInterval)
)
// result.RemoveAt(result.Count - 1)
// result.Add(
// (
// min (fst current) (fst lastInterval),
// max (snd current) (snd lastInterval)
// )
// )
else
result.Add current
result.ToArray()
let actual = mergeIntervals intervals
printfn $"Input: %A{intervals}"
printfn $"Output: %A{actual}"
printfn $"Actual = expected {actual = output}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment