꼽행착오

정수형 배열이 주어지고, 이 배열이 저장하고 있는 값이 해당 위치의 벽의 높이라고 했을 때, 빗물을 받을 수 있는 총량을 구하는 문제

이 문제는 Two Pointer 방식으로 문제를 해결할 수 있었는데, Left 와 Right 에 각각 인덱스 포인터를 두고 이를 이동하면서 문제를 풀이하는 방식이다. 인덱스 포인터를 이동하면서 Left 에서의 최대값과 Right 에서의 최대값을 각각 저장해 두고 현재 인덱스 위치가 이보다 값이 작을 경우 빗물을 받을 수 있게 된다.

예를 들어, 위의 그림에서 left 는 0부터 right 는 11부터 시작한다. left, right 인덱스 위치를 보고 높이가 낮은 쪽을 우선한다.

현재 left 인덱스가 1인 경우, left max (0) 보다 현재 높이가 높으므로 left max 를 갱신한다. 그 다음 left 가 2가 되었을 때, 현재 높이보다 left max 가 크므로 left max 와 현재 높이의 차이만큼 물을 받을 수 있게 된다.

이러한 방식으로 left 와 right 포인터를 각각 이동하며 빗물을 받는 양을 구할 수 있다. 이러한 풀이로 작성한 코드는 다음과 같다.

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, left_max = 0, right_max = 0;
        int left, right;
        for (left = 0, right = height.size() - 1; left < right; ) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                }
                else {
                    ans += left_max - height[left];
                }
                left++;
            }
            else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                }
                else {
                    ans += right_max - height[right];
                }
                right--;
            }
        }
        return ans;
    }
};

정렬되지 않은 정수형 배열 nums 가 주어졌을 때, 배열에서 등장하지 않은 양의 정수 중 가장 작은 수를 찾는 문제

문제 조건으로 시간 복잡도는 O(n), 공간 복잡도는 O(1) 로 주어졌다.

문제에서 주어진 시간 복잡도 조건이 O(n) 이기 때문에 정렬을 하거나 하는 등의 방법은 사용이 불가능했고, 단순히 순차 탐색을 통해서만 문제를 해결해야 했다. 이 문제의 경우 풀이 방법을 고민하다가 다른 사람들의 풀이를 보고 아이디어를 얻어 문제를 풀었는데 그 아이디어는 다음과 같다.

문제에서 찾고자 하는 수는 nums 의 길이가 n 이라고 할 때, 1 ~ n+1 사이에 존재한다.

이 아이디어를 통해 생각한 풀이는, 숫자들을 순서대로 나열하면 그 중 빈 자리가 존재할 것이고, 그 위치에 있어야 하는 수가 정답이 되는 것이다. 그래서 순차적으로 배열을 탐색하고 탐색 과정에서 저장된 수들이 각자 맞는 위치에 들어가 있는 지를 확인하고 그렇지 않다면 자리를 서로 바꿔준다. 

예를 들어 [1, 2, 3, 4, 5] 는 순서대로 숫자들이 들어가 있기 때문에 자리를 바꿔줄 필요가 없지만 [1, 2, 5, 4, 3] 은 [5, 4, 3] 의 자리가 순서에 어긋나므로 [3, 4, 5] 로 변경해 [1, 2, 3, 4, 5] 의 모양을 갖도록 한다. 이렇게 1 부터 n 까지의 수가 차례대로 저장된 경우는 그 다음으로 큰 수인 n + 1 이 문제의 답이 된다. 그렇지 않고 [1, 2, 4, 5, 6] 과 같은 모양을 하게 된다면 이를 원래 자리로 숫자들을 옮기면 [1, 2, 6, 4, 5] 가 될 것이다. 왜냐하면, 6 은 이 배열의 길이 5 보다 큰 수이기 때문에 적절한 위치가 없다. 그러므로 배열 탐색 중 중간에 3이 들어가야 할 위치에 6이 들어가 있고 문제의 답은 3이 된다.

이러한 풀이로 작성한 코드는 다음과 같다.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            // 일단 숫자가 1 ~ n 사이인 지 확인하고
            // 자기 자리 찾아주기
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

빈 칸이 존재하는 Sudoku 게임판을 보고, Sudoku 규칙에 맞게 빈 칸들을 모두 채우는 문제.

이 문제는 Hard 난이도지만, 간단하게 DFS 방식으로 문제 해결이 가능했다. 우선, 빈 칸들의 위치를 찾아 Vector 에 저장하고 각 위치들에 숫자를 1~9 까지 하나씩 넣어 가며 모든 빈 칸들을 채운다. 끝까지 채워진 게 확인되면 실행을 종료하도록 한다.

이러한 풀이로 작성한 코드는 다음과 같다.

struct _POINT {
    int y, x;
};

class Solution {
public:
    vector<_POINT> vp;
    bool check(vector<vector<char>>& board, _POINT loc, int num) {
        int y = loc.y, x = loc.x;
        // 가로
        for (int j = 0; j<9; j++){
            if (board[y][j] - '0' == num){
                return false;
            }
        }
        // 세로
        for (int i = 0; i<9; i++){
            if (board[i][x] - '0' == num){
                return false;
            }
        }
        // 블락
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (board[(y / 3) * 3 + i][(x / 3) * 3 + j] - '0' == num){
                    return false;
                }
            }
        }
        return true;
    }

    int dfs(vector<vector<char>>& board, int idx) {
        if (idx == vp.size())
            return 1;

        for (int num = 1; num <= 9; num++) {
            if (check(board, vp[idx], num)){
                board[vp[idx].y][vp[idx].x] = num + '0';
                int res = dfs(board, idx + 1);
                if (res == 1)
                    return 1;
            }
        }
        board[vp[idx].y][vp[idx].x] = '.';
        return 0;
    }

    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i<9; i++){
            for (int j = 0; j<9; j++){
                if (board[i][j] == '.'){
                    vp.push_back({i, j});
                }
            }
        }
        dfs(board, 0);
    }
};

문자열 s 와, 각각이 동일한 길이를 갖는 단어들 words 가 주어졌을 때 words 를 모두 연결해서 나올 수 있는 substring 을 찾는 문제

예를 들어, s 가 "barfoothefoobarman" 이고 words 가 ["foo","bar"] 이면 words 를 모두 연결했을 때 나올 수 있는 문자열은 "foobar" 와 "barfoo" 두 가지이다. 문자열 s에서 위 문자열은 다음과 같이 나타난다. "barfoothefoobarman". 이 때 반환값은 문자열 s에서 찾고자 하는 문자열 words 의 결합이 나타나는 곳의 시작 위치이다.

이 문제에서 중요한 것은, words 의 결합된 문자열의 시작 위치가 어떤 순서로 반환되는 지는 상관이 없다는 점이다. 문제를 해결하기 위해 생각한 방법은 주어진 words 에서 각각의 word 의 등장 횟수를 저장하고, s 를 순차적으로 탐색하면서 해당 위치에서 부분 문자열이 words 에 주어진 word 중 하나인지, 맞다면 count 값을 증가시켜 각 word 별로 등장 횟수가 words 에서 얻은 정보와 일치하는 지를 확인한다.

이와 같은 풀이로 작성한 코드는 다음과 같다.

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> indexes;
        unordered_map<string, int> counts;
        for (auto word : words) {
            counts[word]++;
        }
        int len = s.length(), n = words.size(), wordLen = words[0].length();
        for (int i = 0; i < len - n * wordLen + 1; i++){
            unordered_map<string, int> seen;
            int j;
            for (j = 0; j < n; j++){
                string word = s.substr(i + j * wordLen, wordLen);
                if (counts.find(word) != counts.end()) {
                    seen[word]++;
                    if (seen[word] > counts[word])
                        break;
                }
                else
                    break;
            }
            if (j == n)
                indexes.push_back(i);
        }
        return indexes;
    }
};

위의 코드는 매 탐색 별로 이전 탐색의 정보를 이용하지 않지만, 보완할 수 있다면 위의 코드를 Sliding Window 기법을 활용해 이전 탐색에 이어서 탐색을 이어갈 수 있도록 하면 성능 면에서 더 효율적으로 동작할 수 있을 것 같다.

두 수 dividend, divisor 가 주어졌을 때 dividend 를 divisor 로 나눈 몫을 구하는 문제

몫을 구하는 문제이기 때문에 나눗셈을 수행하지 않고, 뺄셈으로 나눗셈을 구현하는 방법을 생각해 보았다.

예를 들어, 10 을 3으로 나누면 10 / 3 = 3.333... 이지만 몫만 구할 경우 10 = 3 x 3 이므로 10 = 3 x (2 + 1) 로 표현이 가능하다. 마찬가지로 72 를 7로 나누면 72 / 7 = 10 (몫만) 이고, 72 = 7 x 10 = 7 x (8 + 2) 로 표현이 가능하다.

이처럼 뺄셈으로 표현하기 위해서 divisor 와 2의 승수를 곱한 값을 dividend 에서 빼 나가는 방식으로 문제를 풀이했는데 c++ 에서 int 자료형의 표현 범위로 인한 오류가 발생해서 이는 따로 예외처리 하도록 했다.

위의 풀이로 작성한 코드는 다음과 같다.

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;
        if (divisor == 1)
            return dividend;
        bool neg = (dividend >> 31) ^ (divisor >> 31);
        long dvd = abs(dividend), dvs = abs(divisor);
        int ans = 0;
        while (dvd >= dvs){
            long tmp = dvs, m = 1;
            while ((tmp << 1) <= dvd){
                tmp <<= 1;
                m <<= 1;
            }
            dvd -= tmp;
            ans += m;
        }
        return (neg ? -ans : ans);
    }
};

리스트가 주어졌을 때, 리스트의 노드 k 개씩을 묶어 순서를 반전시키는 문제

리스트 노드들은 다음과 같이 주어진다.

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

리스트를 순차적으로 탐색하면서 매 그룹의 k 번째마다 앞의 노드와 값을 바꾸면 간단히 해결할 수 있다. 하지만 리스트 노드에 이전 노드를 참조하는 포인터 변수는 없기 때문에 이와 같은 방법은 사용이 불가능했다.

마찬가지로 순차적으로 탐색하면서 노드가 가진 값의 순서를 바꿔주는 방법을 생각하다 저장 순서가 서로 다른 스택과 큐를 활용할 수 있겠다는 생각을 했다. 앞에서부터 탐색을 하며 스택에 노드 주소를, 큐에 노드가 가진 값을 저장하고, 스택의 원소 개수가 k 개가 되면 스택과 큐에서 순서대로 노드 주소와 값을 꺼내서 서로를 매칭시켜주면 k 개의 순서를 바꿀 수 있게 된다.

위와 같은 풀이로 작성한 코드는 다음과 같다.

class Solution {
public:
    stack<ListNode*> nodeStack;
    queue<int> numQueue;
    ListNode* reverseKGroup(ListNode* head, int k) {
        for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next){
            numQueue.push(tmp->val);
            nodeStack.push(tmp);
            if (nodeStack.size() == k){
                while (nodeStack.size()){
                    nodeStack.top()->val = numQueue.front();
                    nodeStack.pop();
                    numQueue.pop();
                }
            }
        }
        return head;
    }
};

Valid Number 는 주어진 문자열이 문제의 조건에 맞는 지 확인하는 문제이다.

문제에서 주어진 확인해야 하는 조건은 다음과 같다.

1. 전체 문자열이 Decimal Number / Integer 로 구성되었는가.

(Optional) 지수 표현을 위한 'e' / 'E' 가 등장했을 때 해당 문자 뒤로 Integer 가 나타나는가.

2. Decimal Number 는 부호('+' / '-') 와 소수로 주어진다. 소수는 다음의 3가지 포맷 중 하나이다.

2-1. 하나 이상의 Digit 과 소수점 ex) "2."

2-2. 소수점과 하나 이상의 Digit ex) ".2"

2-3. 하나 이상의 Digit 과 소수점, 그리고 다시 하나 이상의 Digit ex) "2.2"

3. Integer 는 부호('+' / '-') 와 하나 이상의 Digit 으로 이루어진다.

이 조건을 모두 만족하면 함수의 결과값으로 true 를 반환하고, 만족하지 못할 경우 false 를 반환한다.

문제의 해결 방식은 지수 표현을 위한 부분과 그렇지 않은 부분을 나눠서 조건을 검사하는 것이었다.

우선, 문자열의 시작부터 탐색을 하며 문자열이 Sign 과 Digit 으로만 이루어져 있는지를 확인한다.

이 때 Dot 이 문자열에 등장한 경우 Dot 의 개수를 저장해 놓는다. 하나의 Valid Number 가 가질 수 있는 Dot 의 개수는 한 개이다.

또한 지수 문자 'e' / 'E' 가 등장하기 전까지 Digit 의 개수가 최소 1개는 등장해야 하므로 이를 확인한다.

지수 표현을 위한 부분은 위와 유사하게 지수 문자 'e' / 'E' 의 뒤에 Digit 만이 존재하고, Digit 이 한 개 이상 존재하는 지를 확인한다.

마지막으로 Index 가 문자열의 끝에 도달했는 지를 확인하면 주어진 문자열이 Valid Number 인지 확인할 수 있다.

소스 코드는 다음과 같다.

class Solution {
public:
    bool isDecimal(char c) {
        return c >= '0' && c <= '9';
    }

    bool isSign(char c) {
        return c == '+' || c == '-';
    }

    bool isNumber(string s) {
        int i = 0;
        while (s[i] == ' ')
            i++;
        if (isSign(s[i]))
            i++;

        int decimal = 0, dot = 0;
        while (isDecimal(s[i]) || s[i] == '.'){
            if (s[i] == '.'){
                dot++;
            } else {
                decimal++;
            }
            i++;
        }

        if (dot > 1 || decimal < 1)
            return false;

        if (s[i] == 'e' || s[i] == 'E'){
            i++;
            if (isSign(s[i]))
                i++;

            decimal = 0;
            while (isDecimal(s[i])){
                decimal++;
                i++;
            }

            if (decimal < 1)
                return false;
        }

        return s[i] == '\0';
    }
};

# 62. Unique Paths

M * N 크기의 Grid 가 주어졌을 때, Top-Left 부터 Bottom-Right 위치까지 이동하는 유일한 경로의 개수를 구하는 문제

* 이동은 Right, Bottom 방향으로만 가능하다.

오른쪽과 아래로만 이동이 가능하기 때문에 한 위치에서 오른쪽 위치 (몇 번을 이동하든) 로 가는 경로는 하나이고, 아래 방향도 마찬가지이다.

대각선 방향으로 이동하는 것은 오른쪽 -> 아래 / 아래 -> 오른쪽 의 경로만 존재하기 때문에 대각선 방향으로 이동하는 경우는 해당 위치의 바로 위칸까지 이동하는 경로 개수 + 왼쪽 위치로 이동하는 경로 개수로 구할 수 있다.

int uniquePaths(int m, int n) {
	int matrix[101][101] = { 0, };

	for (int j = 0; j < n; j++)
		matrix[0][j] = 1;

	for (int i = 1; i < m; i++) {
		matrix[i][0] = 1;
		for (int j = 1; j < n; j++) {
			matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
		}
	}
	return matrix[m - 1][n - 1];
}

# 63. Unique Paths II

위의 문제와 마찬가지로 M * N 크기의 Grid 가 주어지고 유일한 경로의 개수를 구하는 문제이다.

유일한 차이는 중간에 장애물이 있어 해당 칸으로는 이동이 불가능하다는 점이다.

# 62. 와 풀이는 동일하게 진행하지만, 장애물이 있는 경우는 해당 칸으로 이동하는 경로의 개수를 0으로 만든다.

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int M = obstacleGrid.size(), N = obstacleGrid[0].size();
	if (obstacleGrid[0][0] == 1 || obstacleGrid[M - 1][N - 1] == 1)
		return 0;
	vector<vector<int>> ans(M, vector<int>(N, 0));
	for (int k = 0; k < N; k++) {
		if (obstacleGrid[0][k] != 1)
			ans[0][k] = 1;
		else
			break;
	}

	for (int i = 1; i < M; i++) {
		if (obstacleGrid[i][0] != 1)
			ans[i][0] = ans[i - 1][0];
		else
			ans[i][0] = 0;
		for (int j = 1; j < N; j++) {
			if (obstacleGrid[i][j] == 1)
				ans[i][j] = 0;
			else
				ans[i][j] = ans[i][j - 1] + ans[i - 1][j];
		}
	}
	return ans[M - 1][N - 1];
}

# 64. Minimum Path Sum

M * N Grid 가 주어지고 각각의 칸에는 임의의 값이 들어있을 때 Top-Left 칸에서 Bottom-Right 칸으로 이동할 때 가장 작은 합을 갖는 경로의 합을 찾는 문제

* 위와 마찬가지로 이동은 오른쪽 / 아래 방향으로만 가능하다.

우선 M * N 크기의 행렬을 만들고, 각 칸 별로 최소 합을 만드는 경로를 찾도록 했다.

경로는 위의 문제에서 구했듯 어떤 한 위치로 이동할 수 있는 경우는 해당 위치의 윗칸 / 왼쪽 칸에서 해당 칸으로 이동하는 방법밖에 존재하지 않는다.

따라서 어떤 위치까지 경로의 합의 최소값은 윗칸 / 왼쪽 칸까지의 합 중 작은 값 + 현재 칸의 값이 될 것이다.

int minPathSum(vector<vector<int>>& grid) {
    int N = grid.size(), M = grid[0].size();

    for (int i = 1; i<M; i++)
        grid[0][i] += grid[0][i-1];
    for (int i = 1; i<N; i++)
        grid[i][0] += grid[i-1][0];

    for (int i = 1; i<N; i++){
        for (int j = 1; j<M; j++){
            grid[i][j] += (grid[i-1][j] < grid[i][j-1] ? grid[i-1][j] : grid[i][j-1]);
        }
    }
    return grid[N-1][M-1];
}

# 58. Length of Last Word

주어진 문자열 (문장) 에서 마지막 단어의 길이를 구하는 문제

간단하게 C++ 의 String 내장 메소드 find_last_of / find_last_not_of 를 사용해 문제 해결

int lengthOfLastWord(string s) {
	if (s.find_first_not_of(" ") == -1)
		return 0;
	int last = s.find_last_not_of(" ");
	int first = s.substr(0, last).find_last_of(" ");
	return last - first;
}

# 59. Spiral Matrix II

정수 N 이 주어졌을 때, N * N 크기의 Spiral Matrix 를 만드는 문제

Spiral Matrix 의 값이 증가하는 방향 순서대로 증가하는 값을 넣어주도록 했다.

int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };

    vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>> ans(n, vector<int>(n, 0));
	int dir = 0, cy = 0, cx = 0;
	int max_val = n * n;
	for (int i = 1; i <= max_val; i++) {
		ans[cy][cx] = i;
		int ny = cy + dy[dir], nx = cx + dx[dir];
		if ((ny < 0 || ny >= n || nx < 0 || nx >= n) || ans[ny][nx] != 0) {
			dir = (dir + 1) % 4;
			ny = cy + dy[dir], nx = cx + dx[dir];
		}
		cy = ny, cx = nx;
	}
	return ans;
}

# 61. Rotate List

List 의 Head 가 주어지고, 정수 k 가 주어졌을 때 k 번만큼 오른쪽으로 회전한 리스트를 구하는 문제

처음 생각한 해결 방법은, List 의 tail 부터 탐색해서 해당 node 의 next 링크를 head 로 연결하고 해당 node 를 head 로 변경하는 것이었는데 이 방법은 List 에서 prev link 를 구할 수 없어 구현이 불가했다.

때문에 다시 생각해 낸 방법은, head 부터 끝까지 탐색하면서 각각 node 들이 저장하고 있는 값들을 구하고 그 값을 다시 node 에 순서를 변경해 저장하는 것이었다.

ListNode* rotateRight(ListNode* head, int k) {
	int val[501];
	int size = 0;
	for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
		val[size++] = tmp->val;
	}
	if (size <= 1)
		return head;
	k %= size;
	int idx = (size - k) % size;
	for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
		tmp->val = val[idx];
		idx = (idx + 1) % size;
	}
	return head;
}

# 55. Jump Game

배열이 주어지고 배열의 각 값이 해당 위치에서 다음 인덱스로 Jump 가능한 범위라고 할 때 시작 인덱스부터 마지막 인덱스까지 점프가 가능할 지를 찾는 문제

이 문제는, 시작 인덱스부터 탐색을 하면 각 인덱스에서 점프를 뛰어 갈 수 있는 위치를 일일히 표시해야 해서 시간이 오히려 오래 걸리는 문제였다.

문제 해결이 안 되는 것은 아니지만, 이보다 빠르게 해결할 수 있는 방법이 끝 인덱스부터 탐색을 하는 방법이었다.

뒤에서부터 앞으로 탐색을 하면서 현재 위치에서 내가 저장하고 있는 위치까지 점프를 뛸 수 있으면, 저장하고 있는 위치를 현재 위치로 바꾼 다음 다시 앞으로 탐색을 진행하는 방식이다.

이 방식을 통해 O(N) 으로 탐색이 가능해졌고 문제의 해결을 빠르게 할 수 있었다.

bool canJump(vector<int>& nums) {
	int last = nums.size() - 1;
	for (int i = last - 1; i >= 0; i--) {
		if (i + nums[i] >= last) {
			last = i;
		}
	}
	return (last == 0);
}

# 56. Merge Intervals

Interval 들을 저장하는 배열이 주어졌을 때, 겹치는 Interval 들을 합치는 문제

일단 이 문제를 해결하기에 앞서 Interval 들이 서로 겹쳐지는 지를 확인하기 위해서 배열을 정렬을 한 후 문제를 해결했다.

결과를 저장할 배열을 새로 만들고, 앞에서부터 Interval 이 겹쳐지면 겹쳐진 범위의 최대를 저장하는 식으로 문제를 풀었다.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
	sort(intervals.begin(), intervals.end());

	vector<vector<int>> ans;
	ans.push_back(intervals[0]);

	for (int i = 1; i < intervals.size(); i++) {
		if (ans.back()[1] >= intervals[i][0]) {
			ans.back()[1] = max(ans.back()[1], intervals[i][1]);
		}
		else {
			ans.push_back(intervals[i]);
		}
	}
	return ans;
}

# 57. Insert Intervals

겹치지 않는 Interval 들이 주어졌을 때, 새로운 Interval 을 삽입하는 문제

기존에 있던 Interval 에 겹쳐지는 영역이 있을 수 있기 때문에 해당 부분에 대한 처리가 필요한 문제였다.

새로운 Interval 과 겹치는 Interval 전까지는 그대로 저장하고, 겹치는 Interval 들에 대해서 하나의 Interval 로 만든 다음 해당 Interval 을 결과에 저장하고 남은 Interval 들을 저장하도록 해서 문제를 해결했다.

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
	vector<vector<int>> ans;

	int idx = 0;
	while (idx < intervals.size() && intervals[idx][1] < newInterval[0])
		ans.push_back(intervals[idx++]);

	while (idx < intervals.size() && intervals[idx][0] <= newInterval[1]) {
		newInterval[0] = min(newInterval[0], intervals[idx][0]);
		newInterval[1] = max(newInterval[1], intervals[idx][1]);
		idx++;
	}
	ans.push_back(newInterval);
	while (idx < intervals.size())
		ans.push_back(intervals[idx++]);

	return ans;
}