The Multi-Paradigm Approach

Why you need many ideas for one problem

Today your unmatched intellectual prowess is needed at the airport.

A small city near you has decided to open up a domestic airport to increase travel and business. But they’re new to this whole airport thing and the supervisor of the project, being your friend, requests your help with a problem in the assignment.

Every day, there will be N planes landing in this airport. Since the airport is small, N <= 8. The day has 1440 minutes (24 hours) labelled from 0 (midnight) to 1439 (23:59). For each of the N airplanes, there is an interval between which the plane should land. The i-th plane must land between minutes a[i] and b[i] inclusive during the day. Your job is to create an array, “t”, such that the i-th plane lands at minute t[i] during the day. Note that no 2 planes can land at the same time. However, in order to help the airport cope, the planes should land as far apart as possible. What this means is that the smallest difference between any 2 values in t should be maximised.

Determined to solve this problem, you put on your curious coder’s cap and get to work helping your friend.

Consider an example

Before tackling the problem, you consider an example. So suppose there are on some day 3 planes. The 3 planes need to land within minutes 0-10, 5-15, and 10-15 respectively. In other words,

N = 3
a = [0, 5, 10]
b = [10, 15, 15]

There are many ways you can land the 3 planes, you consider 2 options.

The 2nd method of landing planes, such that t=[0,7,15], actually maximises the minimum gap between the times 2 planes land, in this case 8 minutes.

Splitting up the problem

Among the many different problem solving methods you’ve learnt so far, none will suffice to solve this problem. In fact, there is no one single problem-solving method you can use to obtain the solution to this problem, because there are actually many differnt parts to it.

1. You need to find an order to land the planes in (brute-force)

2. You need to ensure the landings can take place within the time ranges allocated (greedy)

3. You need to space out the landings as much as possible (divide-and-conquer)

So there’s not one, not two, but three different problem-solving methods you need to use to solve this problem. And your curious mind is going to explore each one. Let’s go!

Part 1: Brute force

This technique is similar to the one used to loop through all subsets in a set with bitmasks.

Bitmasks

Except this time, instead of looking through all possible subsets of a set, we’re looking at all possible permutations of a set.

Permutations: different ways of arranging the items of a set

There are only up to 8 planes. How many ways are there to order them? There are 8 ways to choose the first plane to land, 7 ways to choose the next plane to land, and so on. So the total is 8 times 7 times 6 times … all the way to 1, which is 40,320. That’s not a lot for a computer, so you can afford to loop through all of them.

Part 2: Greedy

This problem may look similar to the interval scheduling problem from before.

Greedy Algorithms

Similarly to that problem, there is no way to generalise an order to land the planes, hence we need to try all possible orders. Now how do we check if the order is valid?

Suppose that the minimum gap between plane landing times is some number L. Then we can force all planes to land like this.

Make plane 0 land at a[0]. 

For every next plane j, 
   Make plane j land at max(a[j-1] + L, a[j])

This greedy method ensures we can force all the planes to land with time interval L. Now we need to choose the largest possible value of L for which this can be accomplished. We also need to come up with a way to check if some value of L works.

Important question: why are we doing this? Why something so abstract as imagining a number L?

Answer: We’re essentially using trial-and-error to find the largest value of L, and the reason will become more clear in the next part.

Part 3: Divide-and-conquer

Again, this is no stranger to you. You’ve learnt binary search before.

The sorting problem

So now we need to find out a good way to determine if L works. And there’s an important observation you can make for that.

• If L is small enough to work, then you will be able to land all planes properly. The reason is linked to the next point.

• If L is too big, one of the planes will have to land beyond their b[j] value.

Therefore there exists a range for L. As L increases, it becomes more likely that one of the b[j] values gets exceeded. But instead of trying all possible L values, we can binary search the answer by guessing a number for L.

• Set a range (l,r). Guess L as the mid point, L = 0.5(l+r)

• If L is too big, repeat the guess with smaller range (l,L-1)

• If L is too small, repeat the guess with smaller range (L+1,r)

• Repeat until the range is too small to be divided further

• Initialise with l = 1 (smallest possible L since no 2 planes can land at the same time) and r = 1440 (max possible L to land all planes in a single day).

Trying it out

We can try our idea of guessing L values with the example problem by seeing what happens when L is too small or too big.

Time complexity analysis

The time complexity of this solution is actually quite efficient. There are N! arrangements of planes. For each arrangement, there are log(1440)≈10 possible values of L you need to guess in the worst case. This is more than 100 times better than guessing all 1440 values of L. Finally, for each value of L that you guess, it takes O(N) to confirm if it works. Therefore, the time complexity is O(N x N!). It’s bad, but just enough to handle 8 planes.

Lessons learnt

You present your fully coded solution to your friend, who is pleased with the results. Even your cat Koshka is happy.

You’ve learnt an important problem-solving lesson today. Often times, you can’t solve problems with only one approach. You need to creatively combine approaches to solve a problem. Only then can you discover the true nature of problem solving- discovering creative solutions to problems.

As a matter of fact, this particular combination of problem-solving methods has a name. It’s often called guess-and-check, or trial-and-error, as it relies on creatively guessing solutions in a time efficient manner. But there are other problem solving paradigms too, that can be combined to reveal a whole new world of meaningful solutions to complex problems.

You decide to call it a day. But a curious coder’s mind never rests. You continue to wonder… what other problem solving methods can you combine into one? And is there a faster way to guess and check this problem?

---

There’s a multi-paradigm approach you have to take to support me. It involves pledging your support for my writing and subscribing to never miss a post. After all, it’s hard work writing alone!

And ensure to share this with other curious coders who’d like to engage their minds as much as you.

See ya in the next one!