Missing Soldiers

An infinite army of ants is marching on an infinite 2-D plane. Since ants are disciplined, here's how they march: each ant chooses exactly one x coordinate and moves along it in positive y-direction, starting from (x, 0). There exists exactly one ant for each x coordinate on that plane and hence there are infinite ants!

There are N horizontal barriers lying on this plane. The ith barrier is defined by (xi, yi) and di, which means that the barrier is blocking all ants which want to pass through points lying on line segment connecting (xi, yi) and (xi + di, yi). Once an ant encounters a barrier, it stops moving.

Given all the barriers, your task is to find the total number of ants, that will be ever blocked at some point in their march.

Example:

Input: n = 2, arr = {{1, 1, 4}, {7, 3, 5}}
Output: 11

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> a;

vector<pair<int, int>> merge(const vector<pair<int, int>> &x)
{
    int n = x.size();

    //if size is 1 then return the
    //same vector
    if (n == 1)
        return x;
    vector<pair<int, int>> res;
    res.push_back(x[0]);
    for (int i = 1; i < n; ++i)
    {
        if (x[i].first <= res.back().second)
        {
            res.back().second = max(res.back().second, 
                                   x[i].second);
        }
        else
        {
            res.push_back(x[i]);
        }
    }
    return res;
}

int missingSoldiers(int n, vector<vector<int>> &arr)
{
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        a.push_back(make_pair(arr[i][0], arr[i][0] + arr[i][2]));
    }
    //sort the array
    sort(a.begin(), a.end());
    a = merge(a);
    for (int i = 0; i < a.size(); ++i)
    {
        ans += (a[i].second - a[i].first + 1LL);
    }
    return ans;
}
int main()
{

    int n = 2;

    vector<vector<int>> arr = {{1, 1, 4},
                               {7, 3, 5}};

    cout << missingSoldiers(n, arr) << "\n";
    return 0;
}