Gridland Metro – HackerRank Solution

In this post, we will solve Gridland Metro HackerRank Solution. This problem (Gridland Metro) is a part of HackerRank Problem Solving series.

Solution – Gridland Metro – HackerRank Solution

C++

#include <iostream>
#include <set>
#include <map>
#include<vector>
#include <algorithm>

using namespace std;

int row, col, k;
map<int, vector<pair<int, int>>> in;


long long len(vector<pair<int, int>> & v) {
    sort(v.begin(), v.end());
    auto it = v.begin();

    int a = it->first;
    int b = it->second;
    long long r = 0;
    it++;

    for (; it != v.end(); it++) {
        if (it->first <= b) {
            b = max(b, it->second);
        }
        else {
            r += (b - a + 1);
            a = it->first;
            b = it->second;
        }
    }
    r += (b - a + 1);

    return r;
}

int main() {
    cin >> row >> col >> k;
    while (k--) {
        int r, a, b; cin >> r >> a >> b;
        in[r].push_back(make_pair(a, b));
    }

    long long res = (long long)row * col;

    for (auto &it : in) {
        res -= len(it.second);
    }
    cout << res << endl;
    return 0;
}

Python

from collections import defaultdict

n, m, k = map(int, input().split())

tracks = defaultdict(list)
for _ in range(k):
    row, c1, c2 = map(int, input().split())
    tracks[row].append((c1, -1))
    tracks[row].append((c2 + 1, 1))
    
ans = 0
for row in tracks:
    tracks[row].sort()

    prev = tracks[row][0][0]
    depth = 1
    for event in tracks[row][1:]:
        if depth > 0:
            ans += (event[0] - prev)

        depth -= event[1]
        prev = event[0]
        
print(n * m - ans)
       

Java

import java.util.*;
import java.awt.*;

public class Solution {
    ArrayList<Point> locs;
    
    public Solution(){
        locs = new ArrayList<>();
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long rows = in.nextInt(), cols = in.nextInt();
        int tracks = in.nextInt();
        ArrayList<Integer> check = new ArrayList<>();
        HashMap<Integer, Solution> found = new HashMap<>();
        
        for(int i = 0; i<tracks; i++){
            int curRow = in.nextInt(), start = in.nextInt(), end = in.nextInt();
            if(!found.containsKey(curRow)){
                Solution sol = new Solution();
                sol.locs.add(new Point(start,end));
                check.add(curRow);
                found.put(curRow,sol);
            }else{
                Solution sol = found.get(curRow);
                sol.locs.add(new Point(start, end));
            }
        }
        
        //Computing the total # of tracks - those of train tracks
        long total = rows * cols;
        for(int r : check){
          //  System.out.println(r);
            Solution sol = found.get(r);
            ArrayList<Point> myPoints = sol.locs;
            Collections.sort(myPoints, new myComparator());
            Point first = myPoints.get(0);
            total -= (first.y - first.x+1);
            int lastEnd = first.y+1;
            for(int i = 1; i<myPoints.size(); i++){
                Point curPoint = myPoints.get(i);
                if(curPoint.y< lastEnd) continue;
                int begin = Math.max(curPoint.x, lastEnd);
                total -=(curPoint.y - begin + 1);
                lastEnd = curPoint.y+1;
            }
        }
        
        System.out.println(total);        
    }
}
class myComparator implements Comparator<Point>{
    public int compare(Point p1, Point p2){
        return p1.x - p2.x;
    }
}

Note: This problem (Gridland Metro) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.