Tasks and Ribbons

Tasks and Ribbons

There is a famous problem, that comes up from time to time. I stumbled upon it in several interviews with Big Tech companies.

It has different statements. Sometimes it's like "there are a lot of meetings, you have start and end times,what's the max number of meetings overlapping at some moment in time?". Sometimes: "There is a red ribbon starting at 0 and ends at "a" and several blue ribbons, you have their start points and ends in an array. Is some piece of red ribbon is visible?"

My favorite approach to this class of problems is to split each ribbon (or meeting) into a stream of events: start of meeting, end of meeting (or scanning line meets ribbon, scanning line leaves ribbon).

Then you sort this stream of events and process it. Here you are to pay attention. Because tuples (x, 1) and (x, -1) which correspond to opening and closing events tend to go in unpleasant order. So, either you are to sort in reverse order for the second tuple component, or you introduce weird notation for an opening event as (x, -1) and for closing (x, 1).

So, a lot of nuances. And you really have to think about all this weird stuff, until you are to materialize your count as an array. In this case you can use hash maps and to store the number of opening and closing events at each point. The code is nice and simple.

And one more idea. When you are asked to maximize dot product of two arrays with non-negative numbers, sort them, multiply elements pairwise and sum results.

If this topic is interesting and you want to discuss program line by line, react with 🔥