import java.util.*;
public class Solution 
{
    public static void main (String[] args)
    {
        List<List<Object>> intervals = new ArrayList<>();
            
        List<Object> entries = new ArrayList<>();
            
        //TEST CASE 1 - No issues     PASS
        //entries.add("[1, 3]");
            
        //TEST CASE 2 - No issues     PASS
        //entries.add("[1, 3]");
        //entries.add("[4, 7]");
            
        //TEST CASE 3 - No issues     PASS
        //entries.add("[1, 3]");
        //entries.add("[2, 7]");
            
        //TEST CASE 4 - No issues     PASS
        //entries.add("[1, 3]");
        //entries.add("[4, 7]");
        //entries.add("[8, 9]");
            
        //TEST CASE 5 - No issues     PASS
        //entries.add("[1, 3]");
        //entries.add("[2, 7]");
        //entries.add("[8, 9]");
            
        // I CAN SEE, AS THE OBJECTS HIT 4, SIMILAR TO MY OTHER CODE, THE RESULTS WERE SKEWED....
            
        //TEST CASE 6 - No issues     PASS
        //entries.add("[1, 3]");
        //entries.add("[4, 7]");
        //entries.add("[8, 10]");
        //entries.add("[11, 25]");
            
        
        //TEST CASE 7 - No issues     PASS
        //entries.add("[1, 3]");
        //entries.add("[4, 7]");
        //entries.add("[8, 10]");
        //entries.add("[11, 25]");
        //entries.add("[27, 33]");
        //entries.add("[35, 38]");
        //entries.add("[42, 47]");
        
            
        //TEST CASE 8 -                 PASS
        //entries.add("[1, 3]");
        //entries.add("[2, 7]");
        //entries.add("[6, 10]");
            
        
        //TEST CASE 9 -                 PASS
        //entries.add("[1, 3]");
        //entries.add("[2, 7]");
        //entries.add("[6, 10]");
        //entries.add("[9, 25]");
        //entries.add("[24, 33]");
        //entries.add("[30, 38]");
        //entries.add("[34, 44]");
        
        
        //TEST CASE 10                  PASS 
        //entries.add("[1, 3]");
        //entries.add("[4, 7]");
        //entries.add("[6, 9]");
        //entries.add("[8, 25]");
        
        //TEST CASE 11                PASS
        //entries.add("[1, 3]");
        //entries.add("[2, 7]");
        //entries.add("[8, 9]");
        //entries.add("[19, 45]");
        //entries.add("[40, 52]");
        //entries.add("[58, 61]");
        
        //TEST CASE 12 - Invalid data   (same interval first two objects) - - seems satisfactory output
        //entries.add("[1, 3]");
        //entries.add("[3, 9]");
        //entries.add("[8, 9]");
            
        //TEST CASE 13 - Invalid data   (same interval first two objects) - seems satisfactory output
        //entries.add("[1, 3]");
        //entries.add("[3, 9]");
        //entries.add("[8, 12]");
        //entries.add("[12, 15]");
        
        //TEST CASE 14 - Invalid data  - seems semantically correct
        //entries.add("[1, 3]");
        //entries.add("[4, 9]");
        //entries.add("[8, 2]");
        //entries.add("[9, 2]");
        
        //TEST CASE 15 - undocumented  (same ranges) - seems satisfactory output
        //entries.add("[1, 3]");
        //entries.add("[1, 3]");
        
        //I am now using my improved code to try more strategic scenarios
        //TEST CASE 16 => using a repeat entry
        //entries.add("[2, 2]");
        //entries.add("[2, 2]");
        
        //TEST CASE 17 => using a descending scenario - I will add reference into the item
        //entries.add("[8, 5]");
        //entries.add("[7, 3]");
        
        //TEST CASE 18 => using a ascending scenario - I will add reference into the item
        //not sure if it will always be ascending passing through this area....
        //entries.add("[3, 7]");
        //entries.add("[5, 8]");
        
        //TEST CASE 19 => using ascending and descending
        //entries.add("[3, 7]");  
        //entries.add("[5, 8]");  //ascending
        //entries.add("[6, 4]");  //descending
        
        //TEST CASE 20 => using ascending and descending but matching intervals (FAIL)
        //entries.add("[3, 7]");  
        //entries.add("[5, 5]");  
        //entries.add("[4, 3]");  
        
        
        //TEST CASE 21 => using ascending and descending
        //entries.add("[6, 5]");  
        //entries.add("[5, 8]");  //ascending
        //entries.add("[6, 4]");  //no merge
        
        //TEST CASE 22 => using ascending and descending
        //entries.add("[6, 5]");  
        //entries.add("[5, 4]");  //desc
        //entries.add("[3, 2]");  //desc
        //entries.add("[1, 1]");  //desc
        
        
         //TEST CASE 23 => using ascending and descending
        entries.add("[6, 5]");  
        entries.add("[4, 5]");  //desc
        entries.add("[3, 2]");  //desc
        entries.add("[1, 5]");  //no merge
        
        
        
        
        
            
        intervals.add(entries);
            
        System.out.println("Final outer list: " + mergeIntervals(intervals));
    }
    
    public static List<List<Object>> mergeIntervals(List<List<Object>> intervals) 
    {
        List<List<Object>> outerList = new ArrayList<>();

        List<Object> innerList = new ArrayList<>();

        int counter=0;
        
        String mergeDirection;
        
        String newInterval="";
        
        int numberObjects=0;
        String range;
                
        String startIntervalFirstRange="";
        String endIntervalFirstRange="";
        
        String startIntervalSecondRange="";
        String endIntervalSecondRange="";
        
        String endInterval;
        
        Iterator<List<Object>> it = intervals.iterator();

        for (List <Object> tt: intervals)
        {  
              for (Object s:tt)
            {
                numberObjects++;
            }
            
            for (Object s:tt)
            {
                counter++;
                System.out.println("\nTHIS IS OBJECT: " + s +  " Counter: " + counter);
                    
                range = String.valueOf(s);
                
                if (numberObjects==1)
                {
                    startIntervalFirstRange = range.substring(1, range.indexOf(","));
                    
                    endIntervalFirstRange = range.substring(range.indexOf(" ")+1,range.indexOf("]"));
                    
                    newInterval = "["+startIntervalFirstRange+","+ " " + endIntervalFirstRange+"]";
                    innerList.add(newInterval);
                    System.out.println("1Added into innerlist: " + innerList);
                }
                
                if (counter>2)
                {   
                    String endNewInterval = newInterval.substring(newInterval.indexOf(" ")+1, newInterval.indexOf("]"));
                    
                    startIntervalFirstRange = range.substring(1, range.indexOf(","));
                    System.out.println("start interval first range:" + startIntervalFirstRange);
                    
                    endIntervalFirstRange = range.substring(range.indexOf(" ")+1,range.indexOf("]"));
                    
                    System.out.println("2end interval first range:" + endIntervalFirstRange);
                   
                    System.out.println("2end new Interval :" + endNewInterval);
                    
                                //[4,9],    [8,2]              8>9
                    //I believe the whole if/else can be collapsed into a single if
                      //This area of code requires a big overhaul
                      //we are in this section because the counter >2
                        //here we are concerned with exact reasons for removing an entry
                        //from the list and also adding the merged one... (this can be perspective of going descending or ascending)
                        //OR if it satisfies neither conditions, it would add the range and state it as NOT MERGED
                        
                        //if last item in innerlist is  [4,9] and new object is [8,2], we know straight away
                        //that it would need to be added into the List based on no merge...
                        //but unfortunately it can only be concluded via a process of elimination...
                        //ie ascertaining if the merge overlap is due to ascending or descending first......
                        
                        //But if we focus on the positions of the digits  
                        //[startIntervalSecondRange = 4,  endIntervalSecondRange=9]
                        //[startIntervalFirstRange =8,  endIntervalFirstRange=2]
                        
                        //we know that there is already overlap hence in this loop
                        //also need to remember that startInterval refers to last item in the innerlist
                        //SO USE THIS WITH PRECEDENCE IN ORDER TO AVOID ISSUES since this value is also duplicated with start interval second range
                        
                     //this ascertains an overlap           
                    if (Integer.valueOf(startIntervalFirstRange)<=Integer.valueOf(endNewInterval))
                    {
                        //    2>=4                       &&    9>4
                        //if (endIntervalFirstRange>=startInterval  && endIntervalSecondRange>=startInterval)
                        //{
                            Object lastItemInnerList = innerList.get(innerList.size()-1);
                            System.out.println("Last item inner list: " + lastItemInnerList);
                        
                        String startInterval = String.valueOf(lastItemInnerList).substring(1,String.valueOf(lastItemInnerList).indexOf(","));
                        endInterval = String.valueOf(lastItemInnerList).substring(String.valueOf(lastItemInnerList).indexOf(" ")+1,String.valueOf(lastItemInnerList).indexOf("]"));
                        
                        System.out.println("start interval: " + startInterval);
                        System.out.println("end interval: " + endInterval);
                        System.out.println("start interval second range: " + startIntervalSecondRange);
                        System.out.println("end interval second range: " + endIntervalSecondRange);
                       
                       
                        System.out.println("start interval first range: " + startIntervalFirstRange);
                        System.out.println("end interval first range: " + endIntervalFirstRange);
                        
                        if (startIntervalSecondRange=="" || endIntervalSecondRange=="")
                        {
                            startIntervalSecondRange=startInterval;
                            endIntervalSecondRange=endInterval;
                            
                             System.out.println("populated start interval second range: " + startIntervalSecondRange);
                        System.out.println("populated end interval second range: " + endIntervalSecondRange);
                        }
                        
                        
                        //This classifies as a removal from ascending perspective     or descending perspective
    if ((Integer.valueOf(endIntervalFirstRange)>=Integer.valueOf(endInterval)  && Integer.valueOf(endIntervalSecondRange)>=Integer.valueOf(startInterval))  
    ||  (Integer.valueOf(endIntervalFirstRange)<=Integer.valueOf(endInterval)  && Integer.valueOf(endIntervalSecondRange)<=Integer.valueOf(startInterval)))
                        {
                            
                            
                        System.out.println("1Removed last item from innerList: " + innerList.get(innerList.size()-1));
                        
                        innerList.remove(innerList.size()-1);
                        
                        newInterval = "["+startInterval+","+ " " + endIntervalFirstRange+"]MERGED";
                        innerList.add(newInterval);
                        System.out.println("3Added into Inner List: " + newInterval);
                        System.out.println("This is innerlist: " + innerList);
                        
                        }
                        
                        //}
                        //it would simply have no merging even though the ranges overlap
                        else
                        {
                        newInterval = "["+startIntervalFirstRange+","+ " " + endIntervalFirstRange+"]NO MERGE";
                        innerList.add(newInterval);
                        System.out.println("2Added into Inner List: " + newInterval);
                        }
                    }
                    else
                    {
                        //need to add object here, it is here simply because there is no overlap whatsoever.... 
                        newInterval = "["+startIntervalFirstRange+","+ " " + endIntervalFirstRange+"]NO MERGE";
                        innerList.add(newInterval);
                        System.out.println("11Added into Inner List: " + newInterval);
                    }
                }
                if (counter<=2)
                {
                    if (counter==1)
                    {
                        startIntervalFirstRange = range.substring(1, range.indexOf(","));
                        
                        endIntervalFirstRange = range.substring(range.indexOf(" ")+1,range.indexOf("]"));
                        
                    }
                
                    if (counter==2)
                    {
                        startIntervalSecondRange = range.substring(1, range.indexOf(","));
                        
                        endIntervalSecondRange = range.substring(range.indexOf(" ")+1,range.indexOf("]"));
                        
                        if (Integer.valueOf(endIntervalFirstRange)>Integer.valueOf(startIntervalSecondRange))
                        {
                            //***REPEAT CODE***  required to ascertain direction.....
                            
                            newInterval = "["+startIntervalFirstRange+","+ " " + endIntervalSecondRange+"]A";
                            innerList.add(newInterval);
                            System.out.println("4Added into Inner List: " + newInterval);
                            System.out.println("4*****THE INNERLIST: " + innerList);
                    
                            startIntervalFirstRange="";
                            endIntervalFirstRange="";
                            startIntervalSecondRange="";
                            endIntervalSecondRange="";
                        }
                        else
                        {
                            
                            if (Integer.valueOf(endIntervalFirstRange)<=Integer.valueOf(startIntervalSecondRange))
                            {
                            
                            innerList.add("["+startIntervalFirstRange+","+ " " + endIntervalFirstRange+"]NO MERGE");
                            System.out.println("5Added into Inner List: " + "["+startIntervalFirstRange+","+ " " + endIntervalFirstRange+"]");
                            
                            //this section of code would need to undergo same process as above to ascertain if it can overlap
                            //with the above item added into innerList
                            //this is slightly frustrating since it will enforce first part of repeat code...
                            //but need to use startIntervalSecondRange instead of startInterval
                            //since startInterval is only initialised when counter>2 code above.....
                            
                            //**REPEAT CODE //***********
                                      
                        //This classifies as a removal from ascending perspective     or descending perspective
    if ((Integer.valueOf(endIntervalFirstRange)>=Integer.valueOf(startIntervalSecondRange)  && Integer.valueOf(endIntervalSecondRange)>=Integer.valueOf(startIntervalSecondRange))  
    ||  (Integer.valueOf(endIntervalFirstRange)<=Integer.valueOf(startIntervalSecondRange)  && Integer.valueOf(endIntervalSecondRange)<=Integer.valueOf(startIntervalSecondRange)))
                        {
                            mergeDirection="MERGED";
                            
                            if (Integer.valueOf(endIntervalSecondRange)>Integer.valueOf(endIntervalFirstRange))
                            {
                                mergeDirection="A";
                            }
                            
                            if (Integer.valueOf(endIntervalSecondRange)<Integer.valueOf(endIntervalFirstRange))
                            {
                                mergeDirection="D";
                            }
                            
                            
                        System.out.println("2Removed last item from innerList: " + innerList.get(innerList.size()-1));
                        
                        innerList.remove(innerList.size()-1);
                        
                        newInterval = "["+startIntervalFirstRange+","+ " " + endIntervalSecondRange+"]"+mergeDirection;
                        innerList.add(newInterval);
                        System.out.println("3Added into Inner List: " + newInterval);
                        System.out.println("This is innerlist: " + innerList);
                        
                        }
                        //*************************************
                            else
                            {
                            
                            innerList.add("["+startIntervalSecondRange+","+ " " + endIntervalSecondRange+"]NO MERGE");
                            System.out.println("6Added into Inner List: " + "["+startIntervalSecondRange+","+ " " + endIntervalSecondRange+"]");
                            }
                            
                            }
                            
                            System.out.println("*****THE INNERLIST: " + innerList);
                            newInterval = "["+startIntervalSecondRange+","+ " " + endIntervalSecondRange+"]";
                        }
                    }
                }
                
                
            }
        }
        
        outerList.add(innerList);
        
        return outerList;
    }
}