Algorithms – non-overlapping groups

A technical exploration of one of the algorithms that enables Ellacard's group videos

By Alex Exarhos, May 18, 2021

Do you remember your binary trees? Your recursive graph traversals? Dynamic programming? Odds are, unless you’re currently in an algorithms class, or more likely prepping for a technical interview for a software job, you won’t need to know or use these concepts. I’ve worked at Amazon and Google, and both companies rigorously asked detailed algorithms questions during the interview processes, but it’s much more likely that your day-to-day work will involve wrestling with verbose factory patterns or understanding the nuances of some service API.

I very rarely had a chance to actually work on interesting algorithms at these companies. But this isn’t just another post about the problems of technical interview questions.

At Ellacard, we see all sorts of interesting problems all the time, especially around our group videos. We’ve gone to a lot of effort to make Ellacard look really simple for our users, but behind the scenes, there’s a lot of advanced tech going on to power things like:

We use recursion. We use graph traversals. We use some really complex data structures. And it’s fun and fascinating to solve these problems and be able to deliver an incredible and unique product!

I wanted to share some of these algorithms we’ve had to solve and explain the context so we’re not just imagining some bizarre hypothetical situation like with an interview question… Give them a shot! If you like working on this type of thing, definitely reach out, we’d love to hear from you: contact@ellacard.com

Non-overlapping groups

An Ellacard group video project is made up of multiple individual media resources with details for how / when to show them (videos, images, and audio, but we’ll only worry about video for now). For example, if I just want to cut two videos together back-to-back, my project would effectively say “play video A for 10 seconds, then play video B”.

For our live preview in a web browser, I need to create <video> HTML elements to show the individual resources. There is noticeable overhead to this, and I have to work around some weird autoplay restrictions (that I won’t get into here), however it is possible to replace the src of an existing video element, so the goal is to re-use these video elements as much as possible and create as few of them as possible.

In the example I gave, you can create one <video> element that initially shows video A, and then change it to show video B after 10 seconds. Sometimes however, there might be videos that overlap, like a picture-in-picture type thing. If I wanted video C to start playing from timestamp 5 to 15 seconds, I would need at least two HTML video elements. So the problem is: how can I group my video resources to use the smallest number of video elements possible?

I’ll define a simplified “video resource” as follows:

{
id: 'A', // Unique across all resources
timestamps: [ 0, 10 ] // Assume there will always be ≥ 2 entries
}

Implement a function buildNonOverlappingGroups(resources) that, given an input array of resources as structured above, returns a new array where each element of the output array is itself an array containing the IDs of all the media elements whose automation timestamps do not overlap. The output array should be as short as possible.

My first example from earlier can be written as follows:

[
{ id: 'A', timestamps: [ 0, 10 ] },
{ id: 'B', timestamps: [ 10, 20 ] }
]-> [ [ 'A', 'B' ] ] // One group - A and B share a <video> element

If we introduce the “picture-in-picture” video that overlaps those resources:

[
{ id: 'A', timestamps: [ 0, 10 ] },
{ id: 'B', timestamps: [ 10, 20 ] },
{ id: 'C', timestamps: [ 5, 15 ] }
]-> [ [ 'A', 'B' ], [ 'C' ] ] // Two groups minimum

Here’s a more complicated example that has multiple solutions:

[
{ id: 'A', timestamps: [ 0, 10] },
{ id: 'B', timestamps: [ 1, 2 ] },
{ id: 'C', timestamps: [ 5, 8 ] },
{ id: 'D', timestamps: [ 4, 9 ] },
{ id: 'E', timestamps: [ 3, 6 ] },
{ id: 'F', timestamps: [ 7, 9 ] }
]// Four groups minimum, but multiple solutions!
-> [ [ 'A' ], [ 'B', 'E' ], [ 'D' ], [ 'C', 'F' ] ]
-> [ [ 'A' ], [ 'B', 'E', 'F' ], [ 'D' ], [ 'C' ] ]

Here’s a fiddle — try it for yourself!