Runway reservation system using binary search tree

Runway reservation system

Today, we will discuss a very interesting and real life problem. Let’s say there is a runway, a very busy runway. Flights needs to reserve their landing on this runway in advance, that means reservations are done in future time. ¬†Reservation request contains time of landing. A flight is given landing slot or reservation only if there is no flight schedule to land with K mins of requested landing time. This problem is to design strong>runway reservation system or scheduling system.

There are two notions associated with system involving time. First, adding a reservation to set, i.e insertion operation. Addition of a reservation to set should be done only if constraints are not violated.

Second, if requested reservation time is less than current time, i.e. plane has already landed as per request, that reservation should be removed from the set, so that new reservation requests for that time can be accommodated if they satisfy constraints of the system.

Let’s take an example and see if we understood the problem correctly. Consider current time is t =30 ¬†and we have already scheduled flights at 35, 44 and 57. At t =30, we get another request for landing at t =53. Can we accommodate it? Yes if K =3 as there is no flights scheduled 3 minutes before or after requested reservation time. Hence, now our set become [35, 44, 53, 57]. If at t= 32, another request comes for landing at 45, can we take that? Nope, as it violate 3 min constraints as there is already a landing scheduled at 44. What if request comes for t =25 at t =30. Well, that is not possible as system allows reservation to be done in future only.

This hopefully completely clarifies requirements of system.

Runway reservation system : Data structures

We will consider data structure one by one and see what is best suited for solution in terms of time complexity. Our goal is to achieve, insertion, removal and constraint check in O(log n) time complexity.

First, let’s take unsorted array or list. Store all reservations granted into unsorted array. What is complexity of insertion. It’s O(1) as new reservation will always be added at the end of array. How about constraint check? There is no ordering of reservation, hence you have to scan entire array for constraint check, to see if there is no flight within 3 minutes time of requested reservation time, leading to O(N) complexity. Removal of reservation from unsorted array is also O(N) complexity.

Second, consider sorted array. We have all requests stored in sorted order. What advantage does it give us? Insertion point of new reservation can be found using binary search algorithm with log (N) complexity. That means we can find R[i] which is greater that request time in O(log n) time.

Constraint check can be done by checking R[i] and R[i-1] against requested reservation time, in constant time, hence complexity of O(1).

What happens when we try to insert a request in sorted array? We have to shift all requests greater than request time by one. In worst case, that becomes O(N).

To solve, insertion limitation, we can use sorted list, where insertion complexity is O(1), however, we lose advantage of binary search and finding insertion place becomes O(N). Sorted list solves one problem but worsen another.

How about heaps? Insertion and removal in a heap takes O(log n) time, however, constraint check to check that there is no reservation for landing with K minutes of requested time will take O(n).

Closest we came to our desired time complexity was with sorted array. If we can solve insertion in O(log n) time, we are good to go. That’s where binary search tree comes into picture.

Binary search tree has an invariant which states that all nodes on left side are less and all nodes on right side are greater than the node itself. We will be using this invariant to solve our problem.

As we discussed in post Insert a node in BST, insertion operation is dependent on height of tree, if height of tree is h, then insertion complexity will be O(h), same goes for deletion of node. While constraint check can be done while searching for insertion place in BST, complexity of constraint check also is O(h).

Now, based on nature of tree (balanced or skewed), h may vary between log n to n and hence the insertion, constraint check and removal complexity. So, we are still quite not there.

To make height of binary search tree of order O(log n), we need to somehow balance binary search tree. However, this entire discussion explains how can we arrive at solution of a given problem.

Considering that there is sufficient randomization in reservation request, implementation using simple binary search tree would be like this.

Runway reservation system : Implementation

 Source
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
void inorderTraversal(Node * root){
	if(!root)
		return;
 
	inorderTraversal(root->left);
	printf("%d ", root->value);
	inorderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value, int K){
	if(!node){
		return createNode(value);
	}
	if ( node->value + K > value && node->value - K < value ){
		return node;
	}
	if (node->value > value)
		node->left = addNode(node->left, value, K);
	else
		node->right = addNode(node->right, value, K);
 
	return node;
}
 
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root, 30, 3);
	root = addNode(root, 20, 3);
	root = addNode(root, 15, 3);
	root = addNode(root, 25, 3);
	root = addNode(root, 40, 3);
	root = addNode(root, 38, 3);
	root = addNode(root, 45, 3);
        inorderTraversal(root);
	return 0;
}

Please share if something is wrong or missing. Would love to hear from you. Sharing is caring.