Skip to content

Instantly share code, notes, and snippets.

@mkulak
Created November 3, 2015 22:37
Show Gist options
  • Save mkulak/ef975702edbb6bb7d30d to your computer and use it in GitHub Desktop.
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
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