Created
January 9, 2022 20:07
-
-
Save delneg/45741ec680863483179aebd5a7b470b9 to your computer and use it in GitHub Desktop.
Intervals merge problem in F#, run with `dotnet fsi intervals.fsx`
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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