57. Insert Interval
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[][] insert(int[][] q, int[] ni) {\n        List<int[]> ans=new ArrayList<>();\n        int i=0,start=ni[0],end=ni[1];\n        boolean inserted=false;\n        if(ni.length<=0)\n            return q;\n        while(i<q.length){\n            if((q[i][1]<ni[0])||(q[i][0]>ni[1])){\n                ans.add(q[i]);\n            }\n            else{\n                int []temp=new int[2];\n                inserted=true;\n                start=Math.min(q[i][0],start);\n                while(i<q.length&&q[i][0]<=ni[1]){\n                    i++;\n                }\n                i--;\n                end=Math.max(end,q[i][1]);\n                temp[0]=start;\n                temp[1]=end;\n                ans.add(temp);\n            }\n            i++;\n        }\n        if(!inserted){\n            ans.add(ni);\n            inserted=true;\n        }\n        int[][]res= ans.toArray(new int[ans.size()][]);\n        Arrays.sort(res,(a,b)->Integer.compare(a[0],b[0]));\n        return res;\n    }\n}\n```
['Java']