Java || Short (Beats 99.26%) || PriorityQueue
One Pass (Beats 99.26%) : Code\n\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> list = new ArrayList<
# One Pass (Beats 99.26%) : Code\n```\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> list = new ArrayList<>();\n        /*  \n            Test Case 1.\n            newInterval : [2,5]\n            intervals : [[1,3],[6,9]]\n                                 ^\n        */\n        for (int[] interval : intervals) {\n            if (interval[1] < newInterval[0]) {\n                list.add(interval);\n\n                // second interval[1] =>  [6, 9] > [1, 5]\n            } else if (interval[0] > newInterval[1]) {\n                list.add(new int[] {newInterval[0], newInterval[1]}); // added (1,5)\n                newInterval = interval; // (6,9)\n\n                // first interval[0] => [1, 3] >= [2,5]\n            } else if (interval[1] >= newInterval[0]) {\n                // newInterval = [1, 5]\n                newInterval[0] = Math.min(newInterval[0], interval[0]);\n                newInterval[1] = Math.max(newInterval[1], interval[1]);\n            }\n        }\n        list.add(newInterval); // added (6, 9) => list: [(1, 5), (6, 9)]\n        int[][] res = new int[list.size()][2];\n        for (int i = 0; i < list.size(); i++) {\n            res[i] = list.get(i);\n        }\n        return res;\n    }\n}\n```\n\n\n# PriorityQueue : Code\n```\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));\n        for (int[] interval : intervals) pq.add(interval);\n        pq.add(newInterval);\n        \n        List<int[]> res = new ArrayList<>(); \n        int[] prev = pq.poll();        \n        while (!pq.isEmpty()) {             \n            int[] cur = pq.poll();\n            if (prev[1] >= cur[0]) {\n                prev = new int[]{prev[0], Math.max(cur[1], prev[1])};\n            } else {\n                res.add(prev);\n                prev = cur;\n            }\n        }\n        res.add(prev);       \n        return res.toArray(new int[res.size()][]);\n    }\n}\n```
['Heap (Priority Queue)', 'Java']