Created
November 3, 2015 22:37
-
-
Save mkulak/ef975702edbb6bb7d30d to your computer and use it in GitHub Desktop.
Calculating sum of squares of rectangles, which bottoms are located on one line
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
data class Rect(val left:Float, val right:Float, val height:Float) | |
data class Mark(val rect:Rect, val value:Float, val isFinish:Boolean) | |
fun calcSquare(data:List<Rect>):Float { | |
if (data.isEmpty()) { | |
return .0f | |
} | |
val marks = arrayListOf<Mark>() | |
for (rect in data) { | |
marks.add(Mark(rect, rect.left, false)) | |
marks.add(Mark(rect, rect.right, true)) | |
} | |
val timelapse = marks.sortedBy { it.value } | |
var square = .0f | |
var cur:Float = timelapse.first().value | |
val queue = PriorityQueue<Rect>({f1, f2 -> f2.height.compareTo(f1.height)} ) | |
queue.add(timelapse.first().rect) | |
for (mark in timelapse.drop(1)) { | |
val width = mark.value - cur | |
val height = if (queue.isEmpty()) .0f else queue.peek().height | |
square += width * height | |
cur = mark.value | |
if (mark.isFinish) { | |
while(!queue.isEmpty() && queue.peek().right <= cur) { | |
queue.poll() | |
} | |
} else { | |
queue.add(mark.rect) | |
} | |
} | |
return square | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment