Recently I played solving the overlapping rectangles problem. This problem is simple, it is about finding out among a set of rectangles laid out on a surface which are the ones that overlap, with code of course. I will certainly detail my solution later but since it is very big and requires a bit of work and graphics, I prefer starting by sharing small bricks of the solution now.
A brick of the solution involves scanning the x coordinates of each rectangles like you’re moving from left to right reading every x coordinate of a rectangle you encounter, both left and right side. In computing terms, this means you need a structure to put the x coordinates in, and the scanning means the structure needs to be sorted : first x coordinate is the first coordinate you encounter and therefore the smallest one, last x is the largest.
I picked an array as the data structure so I needed this array to be sorted at all times to track the x coordinates. In real life conditions, the rectangles are thrown at you in chaos order and you have to add the x coordinates to your array and keep it sorted. How would you do that? This is the very problem I intend to expose and solve in this article :
How to keep an array sorted as you insert data in it?
My code is in javascript but the reasoning I will describe is totally language agnostic, you can always apply it to your own language.
Continue reading →
