Tuesday, August 18, 2015

Find minimum number of different type of dishes to be ordered

There are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get at least one dish of his choice. What is the minimum number of different type of dishes we can order? 

Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row. 

n = 6 k = 7 
1 0 0 0 1 0 0 
1 0 0 0 0 1 0 
1 0 0 0 0 0 1 
0 1 0 0 1 0 0 
0 0 1 0 0 1 0 
0 0 0 1 0 0 1 

Output 
3 

Explanation 
Take dish number 5,6,7.


Update the dishes array with the input vector.
N(i) = (N(i) << 1) | V(i)
void updateDishes(vector<string> list, int **dishes)
{
  int index = 0;
  for (vector<string>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    *((*dishes)+index) = (*((*dishes)+index) << 1) | (stoi(*i) & 0x1);
    index++;
  }
}    
  
Read the input file and update the dishes array.
int *CreateArrayFromFile(string filename, int &totalDishes, int &totalPersons)
{

  int *num = NULL;
  string line;
  string buf; 
  ifstream inFile(filename);

  // Read line by line for processing
  while ( getline (inFile, line) )
 {

    // Tokenize the line
    stringstream ss(line);
    vector<string> tokens;

    // Store all the tokens in a vector
    while (ss >> buf)
      tokens.push_back(buf);

    // Allocate the memory for the dishes array
    if (NULL == num)
    {
      totalDishes = tokens.size();
      num = new int[totalDishes]();

#ifdef DEBUG
      for (int i=0; i<tokens.size(); i++)
        cout << i << ": " << num[i] << endl;
#endif

}

    // Update the dishes array with person's like/dislike
    updateDishes(tokens, &num);

#ifdef DEBUG
    for (int i=0; i<tokens.size(); i++)
      cout << i << ": " << num[i] << endl;
    
    printVector(tokens);
#endif
    
    totalPersons++;
  }

  // Return the updates dishes array 
  return num;
}
This counts the numbers of bits set in a given numbers. Its a very silly way of counting bits set :(
 int getOnesCount(int num)
{
  int count = 0;

  while(num)
  {
    count = count + (num & 0x1);
    num = num >> 1;
  }

  return count;
}   
  
It interartes over the range (1..2^n) where n is the total number of dishes and create sets which holds the same number of bits set. This data will be used to find all the possible combinations of the same number of bits set in the range.
void getCombinations(vector < vector <int> > &combinations, int totalDishes, int totalPersons)
{

  // Place holders for all the sets
  for (int i=0; i<totalDishes; i++)
  {
    combinations.push_back(vector <int>());
  }

  // Update the sets
  int end = (1 << totalDishes);
  for (int i=1; i<end; i++)
  {
    combinations[getOnesCount(i)-1].push_back(i);
  }

#ifdef DEBUG
  for (int i=0; i<combinations.size(); i++)
  {
    cout << "Vector " << i+1 << " : " ;
    for (vector<int>::iterator it = combinations[i].begin(); it != combinations[i].end(); ++it)
    {
      cout << *it << " ";
    }
    cout << endl;
  }
  cout << endl;
#endif
  
}    
  
Checks if the given combination (bits set in the given num) satisfies all the persons.
bool doesSatisfy(int *dishes, int num, int totalPersons)
{
  int satisfy = (1 << totalPersons) - 1;
  int result = 0;
  int index = 0;
  bool retval = false;
  
  while (num)
  {
    if (num & 0x1)
      result = result | *(dishes+index);

    index++;
    num = num >> 1;
  }

  if(result == satisfy)
    retval = true;

  return retval;
}    
  
This is our main function.
int findMinDishCount(int *dishes, int totalDishes, int totalPersons)
{
  int start = 0;
  int end = totalDishes - 1;
  int index = (int) ((end - start) / 2);
  int retval = -1;

  // Get the combinations with respect to the number of bits set
  vector < vector <int> > combinations;
  getCombinations(combinations, totalDishes, totalPersons);

 /*
  * Here we are using binary search tree traversal to select the numbers of dishes to
  * satisfy all the persons likes.
  */
  while (start != end)
  {
#ifdef DEBUG    
    cout << "[Start:" << start << "] [End:" << end << "]" << endl;
#endif
    index = (int) (start + ((end - start) / 2));
    
    bool foundMatch = false;

    for (vector<int>::iterator it = combinations[index].begin(); it != combinations[index].end(); ++it)
    {
#ifdef DEBUG      
      cout << "[" << index << "] (" << *it << ") ";
#endif
      if (doesSatisfy(dishes, *it, totalPersons) == true)
      {
        foundMatch = true;
        retval = index;
#ifdef DEBUG
        cout << "true" << endl;
#endif

        // If the combination satisfies all the persons likes, We do not need to check
        // with other combinations from the same set
        break;
      }
#ifdef DEBUG
      cout << "false" << endl;
#endif
    }
    
    if (foundMatch == true)
    {
      end = index;
    }
    else
    {
      if (start == end-1)
      {
        if (end == totalDishes - 1 && doesSatisfy(dishes, combinations[end][0], totalPersons) == true)
        {
          retval = end;
        }
        break;
      }
      start = index;
    }    
  }

  return retval + 1;
}    
  
Here is the helper/wrapper function.
int main(int argc, char **argv)
{
  int totalDishes = 0;
  int totalPersons = 0;
  int *dishes = NULL;

  cout << "Filename: " << argv[1] << endl;
  dishes = CreateArrayFromFile(argv[1], totalDishes, totalPersons);
  cout << "Total Dishes: " << totalDishes << endl;
  cout << "Total Persons: " << totalPersons << endl;
  
  cout << endl;
  printLikesDislikes(dishes, totalDishes, totalPersons);
  
  cout << endl;
  int minDishes = findMinDishCount(dishes, totalDishes, totalPersons);
  cout << "Minimun dishes to statisfy everyone: " << minDishes <<endl;
  
  return 0;
}  
  
Supportive hearders.
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;    
  
These functions will be used to get the output in verbose mode.This will be useful in debugging.
void printVector(vector<string> list)
{
  for (vector<string>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    cout << "[" << *i << "] ";
  }
  cout << endl;
}
  
void printLikesDislikes(int *dishes, int totalDishes, int totalPersons)
{
  string heading = "------------";
  cout << "Dishes   :  ";
  for (int j=1; j<=totalDishes; j++)
  {
    cout << j << " ";
    heading = heading + "--";
  }
  cout << endl << heading << endl;
  
  for (int i=totalPersons-1; i>=0; i--)
  {
    string likeDislike = "";
    for (int j=0; j<totalDishes; j++)
    {
      int pos = 1 << i;
      likeDislike = likeDislike + " " + ((pos & *(dishes+j)) == 0 ? "0" : "1");
    }
    cout << "Person " << totalPersons - i << " : " << likeDislike << endl;
  }
}
  

Thursday, July 30, 2015

Write a function which does zig-zag traverse of binary tree and prints out nodes.

All the header files which are needed
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>
    
Brings all the named entities from std namespace into current declarative region
using namespace std;
    
This is the node structure we use to store the values and form the binary tree. For the simplicity, we use int data type to store the node data.
struct node {
  int val;
  struct node *left;
  struct node *right;
};

    
It prints the vector contents for debug purpose.
void printVector(vector<node *> list)
{
  for (vector<node *>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    if (NULL != *i)
      cout << "[" << (*i)->val << "] -> ";
    else
      cout << "[EMPTY] -> ";
  }
  cout << "NULL" << endl;
}

    
The input vector has all the nodes of a certain level (or depth) in the given tree, stored from left to right. This function is capable of printing either in the same order as the vector is created or in reverse order.
void printLevels(vector<node *>& level, int count, int forward)
{
  
  if (1 == forward) { // Print vector as it is
    for(vector<node *>::iterator it = level.begin(); it != level.end(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  } else { // Print vector in reverse order
    for(vector<node *>::reverse_iterator it = level.rbegin(); it != level.rend(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  }
  cout << endl;
}
    
The main function to trave level by level.
void traverse(node *binaryTree, bool ziczac)
{
  string zz = ziczac? "True":"False";
  cout << "ZicZac: [" << zz << "]" << endl;
  
  int count = 1;             // Initial count for the ROOT node (Level 1)
  int countNext = 0;         // Node count in the Next Level
  int forward = 1;           // Decides how to print the list
  vector<node *> nodeList;   // Store nodes level-by-level
  node *tmp = NULL;          // Store the node pointer temporarily 

  // Push the ROOT
  nodeList.push_back(binaryTree);
  
  while (0 != count) {
    // Print the nodes from the current level
    printLevels(nodeList, count, forward);
    
    // Iterate the nodes from current level and get the nodes from
    // the next level
    countNext = 0;
    for (int i=0; i<count;){
      tmp = nodeList.front();

      // Remove the node which is getting processed
      nodeList.erase(nodeList.begin());

      // Node is NULL. Don't count the NULL nodes
      if (NULL == tmp) {
        nodeList.push_back(NULL);
        nodeList.push_back(NULL);
      } else {
        i++;
      
        // Check the left child node
        if (tmp->left) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->left);
        } else {
          nodeList.push_back(NULL);
        }
        
        // Check the right child node
        if (tmp->right) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->right);
        } else {
          nodeList.push_back(NULL);
        }
      }
    }

    // update the current with the level count from the next level
    count = countNext;
    
    if (true == ziczac) {
      // Toggle the way the level is getting printed
      forward = (forward ^ 0x1) & 0x1;
    }
  }
}
    
Read the file with the following format,
('|' is the delimitor)
   1
   2|3
   4|5| |7
   8|9|0|1| | |2|3

and create the binary tree
node *createBinaryTreeFromFile(string filename)
{
  node *binaryTree = NULL;
  vector<node *> nodeList;
  vector<node *> childNodeList;
  vector<string> stringList;
  string line;
  
  try {

    // Open the given file
    ifstream inFile (filename);

    while ( getline (inFile, line) )
    {
      // First Line => ROOT node
      if (NULL == binaryTree) {
        binaryTree = new node;
        binaryTree->val = stoi(line);
        binaryTree->right = NULL;
        binaryTree->left = NULL;
        nodeList.push_back(binaryTree);
      } else {
        stringList.clear();
        string::size_type prev_pos = 0, pos = 0;
        // Split the line with '|' delimitor 
        while( (pos = line.find('|', pos)) != string::npos )
        {
          std::string substring( line.substr(prev_pos, pos-prev_pos) );
          stringList.push_back(substring);
          prev_pos = ++pos;
        }
        string substring( line.substr(prev_pos, pos-prev_pos) ); // Last word
        stringList.push_back(substring);

        // Create the binary tree here (level by level)
        vector<string>::iterator itStringList = stringList.begin();
        while (!nodeList.empty()) {
          
          if (itStringList >= stringList.end())
            break;

          if (NULL == *(nodeList.begin())) {
            itStringList = itStringList + 2;
          } else {
            // Left Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->left = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }

            // Right Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->right = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }
          }
          
          // Remove the node which is getting processed
          nodeList.erase(nodeList.begin());
        }
      }
    }
    inFile.close();
  } catch (ifstream::failure e) {
    cerr << e.what() << endl;
  }

  // Print the tree
  traverse(binaryTree, false);
  
  return binaryTree;
}
    
Everything starts from here,

int main(int argc, char** argv)
{
  node *binaryTree = createBinaryTreeFromFile(argv[1]);
  traverse(binaryTree, true);
  return 0;
}

Monday, July 6, 2015

Bash - Few shortcuts to make our life easier


Navigate the cursor inside the current command statement
Ctrl + a - Start of the command
Ctrl + e - End of the command
Ctrl + f - Move to the next character
Ctrl + b - Move to the previous character
Alt + right_arrow - End of the current word or the next word
Alt + left_arrow - Start of the current word or the previous word
                      
Delete
Ctrl + k - Delete from current cursor position to the end of the command
Ctrl + u - Delete from current cursor position to the start of the command
Ctrl + w - Delete one word before the cursor
Ctrl + h - Delete one character before the cursor (Backspace)
Ctrl + d - Delete the current character under the cursor
                      
Search History
Ctrl + r - Find the command with the phrase you type.It searches the
history as you type. For each consecutive hit "Ctrl + r", it finds the
next match in the history and moves to the start of the history.
!! - Repeat the last command
!xyz - Find the latest command starting with xyz from the history and run it
!xyz:p - Print the latest command starting with xyz from the history
!$ - Last argument of previous command
!* - All arguments of previous command
^abc^def - Replace abc with def in the previous command and run it
                      
Process
$$ - Gets the pid of the current bash/script
$! - Pid of the last background process
$? - Exit status of the last command
                      

Tuesday, June 16, 2015

Given a max-heap represented as an array, return the kth largest element without modifying the heap.


  Here are all the header files included to make the compilation successful.
 

    
#include <iostream>
#include <vector>
#include <stack>

#include <math.h>
using namespace std;
 

    
  This is how we heapify the given array of elements.
  

#define SWAP(x,y) \
  x = x ^ y;      \
  y = x ^ y;      \
  x = x ^ y;      \

void siftDown(vector<int> &v, int start, int end)
{
  int root = start;

  while (root*2+1 <= end){
    int child = root*2+1;
    int swap = root;

    if (child <= end && v[swap] < v[child]) {
      swap = child;
    }
    if(child+1 <= end && v[swap] < v[child+1]) {
      swap = child+1;
    }

    if (swap != root) {
      SWAP(v[root], v[swap]);
      root = swap;
    } else {
      return;
    }
  }
}

void heapify(vector<int> &v, int count)
{

  int start = floor((count-2)/2);

  while (start >=0 ) {
    siftDown(v, start, count-1);
    start = start - 1;
  }
}

 

    
  We modify the stack functionality a little to maintain the element order in the stack with the incoming elements.
  
void insertToStack(vector<int> &v, stack<int> &s, int val)
{
  /* Temporary vector to keep the order from the stack */
  vector<int> tmp;

  /* Pop the elements till new value finds its place */
  while(!s.empty() && v[s.top()] > v[val]){
    tmp.insert(tmp.begin(), s.top());
    s.pop();
  }

  /* push the new value into the stack */
  s.push(val);

  /* Push all the elements in the same order 
     which are previously popped out */
  vector<int>::iterator it;
  for (it=tmp.begin(); it<tmp.end(); it++) {
    s.push(*it);
  }
}

 
    
  This function traverses the heap to find the Kth element in log time
  
int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
{
  /* If current element is smaller than the element in the stack,
     update the current element with the top of the stack and 
     push the current element into the stack*/
  if (!s.empty() && v[s.top()] > v[index]) {
    insertToStack(v, s, index);
    index = s.top();
  }

  if (pos == count) {
    /* If the count reaches pos, return the current element */
    return v[index];
  } else {
    int lchild = index*2+1;
    int rchild = lchild+1;

    /* Check if the current element has right child */
    if (rchild > v.size()-1) {
      
      /* Check if the current element has left child */
      if (lchild > v.size()-1) {
        
        /* The current element is the leaf node. Get the top of 
           the stack to proceed further */
        index = s.top();
        s.pop();
      } else {
        
        /* The current element has only left child. */
        if (s.empty() || v[lchild] > v[s.top()]) {
          index = lchild;
        } else {
          index = s.top();
          s.pop();
          insertToStack(v, s, lchild);
        }
      }
    } else {
      
      /* Find the max and min from the child nodes */
      int max = 0;
      int min = 0;
      if (v[lchild] > v[rchild]) {
        max = lchild;
        min = rchild;
      } else {
        min = lchild;
        max = rchild;
      }

      /* Find the highest element among the child nodes & the top
         of the stack, Update the current element with the highest 
         element and push the other two elements into the stack */
      if (s.empty()) {
        insertToStack(v, s, min);
        index = max;
      } else {
        int top = s.top();
        if (v[max] < v[top]) {
          index = top;
          s.pop();
          insertToStack(v, s, min);
          insertToStack(v, s, max);
        } else {
          index = max;
          if (v[min] > v[top]) {
            insertToStack(v, s, min);
          } else {
            s.pop();
            insertToStack(v, s, min);
            insertToStack(v, s, top);
          }
        }
      }
    }
    
    /* Call "find" recursively till "count" reaches "pos" */
    return find(v, s, index, pos, count+1);
  }
}

int findElement(vector<int> &v, int pos)
{
  /* Start with am empty stack */
  stack<int> s;
  return find(v, s, 0, pos, 1);
}
 
  You are NOT A FAN of recursion? Here you go,
 
@@ -1,5 +1,6 @@
 int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
 {
+  while (count <= v.size()) {
   /* If current element is smaller than the element in the stack,
      update the current element with the top of the stack and 
      push the current element into the stack*/
@@ -74,8 +75,7 @@
         }
       }
     }
-    
-    /* Call "find" recursively till "count" reaches "pos" */
-    return find(v, s, index, pos, count+1);
+    }
+    count++:
   }
 }
 
  Here is the main function
    
int main(int argc, char **argv)
{

  /* Store the inputs into a vector */
  vector<int> input;
  int total= stoi(argv[1]);
  for(int c=0; c<total; c++){
    input.insert(input.end(), stoi(argv[c+2]));
  }

  /* Print them */
  vector<int>::iterator it;
  cout << "     my vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl;

  /* Heapify the input vector */ 
  heapify(input, total);
  cout << "my heap vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl << endl;

  for (int count=1; count<=total; count++) {
    int ret = findElement(input, count);
    cout << "(" << count << "):  " << ret << endl;
  }
  return 0;
}
Output:
$ ./kthInHeap 4 10 6 9 1
     my vector contains: 10 6 9 1
my heap vector contains: 10 6 9 1

(1):  10
(2):  9
(3):  6
(4):  1


$ ./kthInHeap 7 5 6 1 3 8 9 2
     my vector contains: 5 6 1 3 8 9 2
my heap vector contains: 9 8 5 3 6 1 2

(1):  9
(2):  8
(3):  6
(4):  5
(5):  3
(6):  2
(7):  1


$ ./kthInHeap 8 6 5 3 1 8 7 2 4
     my vector contains: 6 5 3 1 8 7 2 4
my heap vector contains: 8 6 7 4 5 3 2 1

(1):  8
(2):  7
(3):  6
(4):  5
(5):  4
(6):  3
(7):  2
(8):  1

Wednesday, June 10, 2015

Reconstruct the itinerary in order


Given an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO]
please reconstruct the itinerary in order, 
[ CDG, MUC, LHR, SFO, SJC ]. 
Note: tickets can be represented as nodes

#!/usr/bin/env python

import sys

# Reads the given file which contains airline tickets
# and returns 2 hash,
#  * (1) with all the ticket info
#  * (2) wth the starting and ending points
def getTicketsFromFile(filename):
    lines = []

    # Read the file
    with open(filename, "r") as fp:
        lines = lines = fp.readlines()

    lines = map(lambda s: s.strip(), lines)

    tickets = {}
    points = {}
    for line in lines:
        if line !="":
            point = map(lambda s: s.strip(), line[1:-1].split(","))
            tickets[point[0]] = point[1]

            # create 2 nodes for each ticket (start, end) and
            # do this for all the tickets
            for p in point:
                try:
                    # Delete the key from the points if it exists to find the start and end
                    # points for the entire trip.
                    del points[p]
                except:
                    points[p] = ""

    # Find the starting point
    for k in points.keys():
        if k in tickets.keys():
            startPoint = k
            break
        
    return (tickets, startPoint)


if __name__ == "__main__":
    (tickets, startPoint) = getTicketsFromFile(sys.argv[1])

    # print the order
    point = startPoint
    while True:
        print point,
        
        try:
            point = tickets[point]
        except:
            break

Thursday, June 4, 2015

Write a function that subtract two integer streams


You are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit.
For example, integer 2048 is represented in the stream as 8, 4, 0, 2. 

Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.

#include <stdio.h>

/* Subtracts two single digits, prints the reminder and returns 1(carry) if a<b */
int subtract(char c_a, char c_b)
{
  /* Convert the char to interger */
  int i_a = c_a - '0';
  int i_b = c_b - '0';
  int ret = 0;

  /* If a<b, increase 'a' by 10 and return 1(carry) to subtract it from 'a' of the next set */
  if (i_a < i_b) {
    i_a += 10;
    ret = 1;
  }
  
  printf ("%d", i_a - i_b);

  return ret;
}


int main(int agrc, char **argv)
{
  /* Get the two operand streams from input arguments */
  char *s_a = argv[1];
  char *s_b = argv[2];

  int carry_one = 0;
  
  /* Pass one char at a time from each input arguments to function subtract */
  while(*s_b != '\0'){
    /* Subtract carry_one from first operand before sending it to function subtract */
    carry_one = subtract(*s_a - carry_one, *s_b);
    s_a++;
    s_b++;
  }

  /* Print the remining digits from the first operand */
  while(*s_a != '\0'){
    printf("%c", *s_a - carry_one);
    s_a++;
    carry_one = 0;
  }
  printf("\n");
  
  return 0;
}
Output:
  $ ./str_subtract 00051 1005 | rev
  09999
  
  $ ./str_subtract 5 3 | rev
  2
  
  $ ./str_subtract 1234 1233 | rev
  1000

Tuesday, June 3, 2014

Find the conflicting appointments

#include <stdio.h>
#include <stdlib.h>

/* 
   Time interval format: yyymmddhhmm yyyymmddhhmm 

   Example Input:
   --------------
   4
   5 6
   1 9
   7 8
   2 10

   Process:
   --------

   Data Structure
   time_node to store the intervals
    ------------------------------
   | timestamp | is_start | index |
    ------------------------------

   Step 1:
   -------

   - stores the timestamps into an array
   
    -----------   -----------   -----------   -----------
   | 5 | 1 | 0 | | 6 | 0 | 0 | | 1 | 1 | 1 | | 9 | 0 | 1 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 2 | 1 | 3 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7

   Step 2:
   -------

   - Sort the array wrt the timestamp value

    -----------   -----------   -----------   -----------
   | 1 | 1 | 1 | | 2 | 1 | 3 | | 5 | 1 | 0 | | 6 | 0 | 0 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 9 | 0 | 1 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7
   
   Step 3:
   -------

     3.1 Push the index value to the index_list if it is the start of an interval
     3.2 Delete the index value from the index_list if it is the end of an interval
       3.2.1 add all the index values from the index_list to the conflict_list of the this interval
       3.2.2 add this interval index into the conflict_list of all the index values in the index_list
*/


/* Index to find parent and the childern */
#define LEFT(a) (2*(a+1) -1)
#define RIGHT(a) (2*(a+1))
#define PARENT(a) ((a-1)/2)

typedef enum boolean {
  FALSE = 0,
  TRUE = 1
} bool;

/* To store the calendar appointment intervals */
typedef struct time_node time_node;
struct time_node {
  unsigned long long timestamp;
  bool is_start;
  int index;
};

/* To store the conflicts */
typedef struct index_node index_node;
struct index_node {
  int index;
  index_node *next;
};

/* Swap function */
#define XORSWAP(a, b) ((a.timestamp)^=(b.timestamp),(b.timestamp)^=(a.timestamp),(a.timestamp)^=(b.timestamp), \
                         (a.is_start)^=(b.is_start),(b.is_start)^=(a.is_start),(a.is_start)^=(b.is_start), \
                         (a.index)^=(b.index),(b.index)^=(a.index),(a.index)^=(b.index))

/* Heapify */
void maxheapify (time_node *list, int count, int index)
{
  int left = LEFT (index);
  int right = RIGHT (index);
  
  int largest = index;
  
  if (left <= count-1 && list[left].timestamp > list[largest].timestamp)
    largest = left;
  if (right <= count-1 && list[right].timestamp > list[largest].timestamp)
    largest = right;
  
  if (largest != index)
  {
    XORSWAP (list[index], list[largest]);
    maxheapify (list, count, largest);
  }
}

/* Buids the heap */
void build_max_heap (time_node *list, int count)
{
  for (int i = (count-1)/2; i >= 0; i--)
  {
    maxheapify (list, count, i);
  }  
}

/* Sorts the intervals using heap sort */
void heap_sort (time_node *list, int count)
{
  build_max_heap (list, count);
  
  int tmp_count = count-1;
  for (int i = count-1; i > 0; i--)
  {
    XORSWAP (list[0], list[i]);
    maxheapify (list, i, 0);
  }
}

/* Adds the index node into the list */
bool add_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    *list = (index_node *) calloc (1, sizeof (index_node));
    if (NULL == *list)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      (*list)->index = index;
      (*list)->next = NULL;
    }
  }
  else
  {
    index_node *t = *list;
    
    while (NULL != t->next)
      t = t->next;

    t->next = (index_node *) calloc (1, sizeof (index_node));
    t = t->next;

    if (NULL == t)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      t->index = index;
      t->next = NULL;
    }
  }
  return TRUE;
}

/* Deletes the index node from the list */
void delete_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    return;
  }
  else
  {
    index_node *t = *list;
    index_node *lbo = *list;

    while (t->index != index)
    {
      if (t->next->next == NULL)
      {
        lbo = t;
      }
      t = t->next;
    }
    
    if (t == *list)
    {
      *list = (*list)->next;
      free (t);
    }
    else if (NULL == t->next)
    {
      lbo->next = NULL;
      free(t);
    }
    else
    {
      t->index = t->next->index;
      index_node *d = t->next;
      t->next = t->next->next;
      free (d);
    }
  }
}

int main (int argc, char **argv)
{
  time_node *interval_list = NULL;

  /* Reads the input file for the intervals */
  FILE *fp = NULL;
  fp = fopen ("intervals.txt", "r");
  if (NULL == fp)
  {
    fprintf (stderr, "Error: Could not read the file.");
    return -1;
  }

  int count = 0;
  int readcount = 0;
  int tmp_count = 0;
  
  /* Reads the count */
  readcount = fscanf (fp, "%d", &count);
  if (0 >= readcount)
  {
    fprintf (stderr, "Error: Nothing in the file.");
    return -2;
  }
  
  interval_list = (time_node *) calloc (count*2, sizeof (time_node));
  if (NULL == interval_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* Reads the intervals */
  printf ("Input:\n");
  for(tmp_count = 0; tmp_count < count; tmp_count++)
  {
    if (feof(fp))
    {
      break;
    }
    unsigned long long start = 0;
    unsigned long long end = 0;
    readcount = fscanf (fp, "%llu %llu", &start, &end);
    printf ("%5d) : %llu <-> %llu\n", tmp_count+1, start, end);
    interval_list[tmp_count*2].timestamp = start;
    interval_list[tmp_count*2].is_start = TRUE;
    interval_list[tmp_count*2].index = tmp_count;
    interval_list[tmp_count*2+1].timestamp = end;
    interval_list[tmp_count*2+1].is_start = FALSE;
    interval_list[tmp_count*2+1].index = tmp_count;
  }
  printf ("\n");
  fclose(fp);

  /* Sort the timestamp values */
  heap_sort (interval_list, count*2);
  
  index_node *index_list = NULL;
  index_node **conflict_list = NULL;
  conflict_list = (index_node **) calloc (count, sizeof (index_node*));
  if (NULL == conflict_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* main loop to find the conflicts */
  for (int i = 0; i < count*2; i++)
  {
    if (interval_list[i].is_start == TRUE)
    {
      if (FALSE == add_index_node (&index_list, interval_list[i].index))
      {
        fprintf (stderr, "Error: Memory allocation failed.");
        return -3;
      }
    }
    else
    {
      delete_index_node (&index_list, interval_list[i].index);

      index_node *t = index_list;
      while (t)
      {
        if (FALSE == add_index_node (&(conflict_list[interval_list[i].index]), t->index) || 
            FALSE == add_index_node (&(conflict_list[t->index]), interval_list[i].index))
        {
          fprintf (stderr, "Error: Memory allocation failed.");
          return -3;
        }
        t = t->next;
      }
    }
  }

  /* Print the result */
  printf ("Conflicts:\n");
  for (int i = 0; i < count; i++)
  {
    printf ("%5d : ", i+1);
    index_node *t = conflict_list[i];
    while (t)
    {
      printf ("%d ", t->index+1);
      t = t->next;
    }
    printf ("\n");
  }
  return 0;
}
We can use self-balanced binary search tree to keep the index_list to get a better time complexity.