/**********************************************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : LT-1-ODD-A
* Description : Insert Set of Intervals into Existing Set of Intervals
**********************************************************************/

#include <stdio.h>

#define MAX 100000

int main()
{
    int n, m, t, i, j, cont;
    int existLeftInterval[MAX], existRightInterval[MAX];
    int newLeftInterval[MAX], newRightInterval[MAX];
    int finalLeftInterval[MAX], finalRightInterval[MAX];
    
    // scanning existing interval information from user
    printf("Enter Number of Existing Intervals: ");
    scanf("%d", &n);
    printf("Enter %d Existing Intervals:\n", n);
    for (i=0; i<n; i++) {
        printf("\tEnter Interval-%d: ", i+1);
        scanf("%d", &existLeftInterval[i]);
        scanf("%d", &existRightInterval[i]);
    }
    // scanning new (to be inserted) interval information from user
    printf("\nEnter Number of New Intervals: ");
    scanf("%d", &m);
    printf("Enter %d New Intervals to Insert:\n", m);
    for (i=0; i<m; i++) {
        printf("\tInsert Interval-%d: ", i+1);
        scanf("%d", &newLeftInterval[i]);
        scanf("%d", &newRightInterval[i]);
    }

    // printing existing interval information
    printf("\n++ Existing Intervals:");
    for (i=0; i<n; i++) {
        printf(" [ %d, %d ];", existLeftInterval[i], existRightInterval[i]);
    }
    // printing inserting interval information
    printf("\n++ Inserting Intervals:");
    for (i=0; i<m; i++) {
        printf(" [ %d, %d ];", newLeftInterval[i], newRightInterval[i]);
    }
    
    for(i=0,j=0,t=0,cont=0; (i<n)&&(j<m); ) {
        // inserting all existing intervals that ends before the start of the first new interval
        if (existRightInterval[i] < newLeftInterval[j]){
            finalLeftInterval[t] = existLeftInterval[i];
            finalRightInterval[t] = existRightInterval[i];
            t++; i++;
        }
        // inserting all new intervals that ends before the start of the first existing interval
        else if (newRightInterval[j] < existLeftInterval[i]) {
            finalLeftInterval[t] = newLeftInterval[j];
            finalRightInterval[t] = newRightInterval[j];
            t++; j++;
        }
        // when new interval overlaps with current existing interval
        else {
            // start of the new interval is before or equal-with the start of the existing interval
            if (newLeftInterval[j] <= existLeftInterval[i]) {
                if (!cont) { // in case of fresh interval to be opened (discontinuous)
                    finalLeftInterval[t] = newLeftInterval[j];
                }
                // end of the new interval is before or equal-with the end of the existing interval
                if (newRightInterval[j] <= existRightInterval[i]) {
                    // next inserted interval starts before or equal-with the end of current existing interval (continuity)
                    if ((j<m-1) && (newLeftInterval[j+1] <= existRightInterval[i])) {
                        j++;
                        cont = 1;  // continuity in interval found -- setting continuity flag
                    }
                    // next inserted interval starts after the end of current existing interval (discontinuity)
                    else {
                        finalRightInterval[t] = existRightInterval[i];
                        i++; j++; t++;
                        cont = 0;  // discontinuity in interval found -- resetting continuity flag
                    }
                }
                // end of the new interval is after the end of the existing interval
                else {
                    // next existing interval starts before or equal-with the end of current inserting interval (continuity)
                    if ((i<n-1) && (existLeftInterval[i+1] <= newRightInterval[j])) {
                        i++;
                        cont = 1;  // continuity in interval found -- setting continuity flag
                    }
                    // next existing interval starts after the end of current inserting interval (discontinuity)
                    else {
                        finalRightInterval[t] = newRightInterval[j];
                        j++; i++; t++;
                        cont = 0;  // discontinuity in interval found -- resetting continuity flag
                    }
                }
            }
            // start of the new interval is somewhere in-between (after the start of) the current existing interval
            else {
                if (!cont) { // in case of fresh interval to be opened (discontinuous)
                    finalLeftInterval[t] = existLeftInterval[i];
                }
                // end of the new interval is before or equal-with the end of the existing interval
                if (newRightInterval[j] <= existRightInterval[i]) {
                    // next inserted interval starts before or equal-with the end of current existing interval (continuity)
                    if ((j<m-1) && (newLeftInterval[j+1] <= existRightInterval[i])) {
                        j++;
                        cont = 1; // continuity in interval found -- setting continuity flag
                    }
                    // next inserted interval starts after the end of current existing interval (discontinuity)
                    else {
                        finalRightInterval[t] = existRightInterval[i];
                        i++; j++; t++;
                        cont = 0;  // discontinuity in interval found -- setting continuity flag
                    }
                }
                // end of the new interval is after the end of the existing interval
                else {
                    // next existing interval starts before or equal-with the end of current inserting interval (continuity)
                    if ((i<n-1) && (existLeftInterval[i+1] <= newRightInterval[j])) {
                        i++;
                        cont = 1; // continuity in interval found -- setting continuity flag
                    }
                    // next existing interval starts after the end of current inserting interval (discontinuity)
                    else {
                        finalRightInterval[t] = newRightInterval[j];
                        j++; i++; t++;
                        cont = 0;  // discontinuity in interval found -- setting continuity flag
                    }
                }
            }
        }
    }
    // inserting all remaining existing intervals
    while (i < n) {
        finalLeftInterval[t] = existLeftInterval[i];
        finalRightInterval[t] = existRightInterval[i];
        i++; t++;
    }
    // inserting all remaining new intervals
    while (j < m) {
        finalLeftInterval[t] = newLeftInterval[j];
        finalRightInterval[t] = newRightInterval[j];
        j++; t++;
    }

    // printing updated interval information after insertion
    printf("\n++ Final Intervals:");
    for (i=0; i<t; i++) {
        printf(" [ %d, %d ];", finalLeftInterval[i], finalRightInterval[i]);
    }
    if(t==0) printf(" NIL");
    printf("\n");

    return 0;
}