# HackerRank Gridland Metro problem solution

In this HackerRank Gridland Metro problem solution we have given a map of Gridland and its k train tracks, find and print the number of cells where the mayor can place lampposts.

## Problem solution in Python.

```#!/usr/bin/env python3

def overlapped(c1, c2, g1, g2):
if c1 == g2+1 or g1 == c2+1:
return True
elif g1 <= c1 <= g2 or g1 <= c2 <= g2:
return True
elif c1 <= g1 <= c2 or c1 <= g2 <= c2:
return True

def update_gridland(r, c1, c2):
if r not in gridland:
gridland[r] = []
gridland[r].append((c1,c2))
else:
for i in range(len(gridland[r])):
if overlapped(c1, c2, gridland[r][i][0], gridland[r][i][1]):
gridland[r][i] = (min(c1, gridland[r][i][0]), max(c2, gridland[r][i][1]))
break
gridland[r].append((c1, c2))

n, m, k = list(map(int, input().strip().split()))
tracks = []
for i in range(k):
tracks.append(tuple(map(int, input().strip().split())))
tracks = tuple(tracks)

gridland = {}
for t in tracks:
r, c1, c2 = t
update_gridland(r, c1, c2)

used = 0
for row in gridland:
for tracks in gridland[row]:
used += abs(tracks[0]-tracks[1])+1

print(n*m - used)```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

static class MyRow {
Long start = null;
Long stop = null;

long add(long start, long stop) {
if(this.start == null || this.stop == null) {
this.start = start;
this.stop = stop;
return this.stop - this.start + 1;
}

long newTracks = 0;
if(start < this.start) {
if(stop < this.start) {
newTracks = stop - start + 1;
} else {
long before = this.start - start;
if(stop <= this.stop) {
newTracks = before;
} else { //(stop > this.stop)
//both sides
newTracks = before + (stop - this.stop);
}
}
this.start = start;
} else if(stop > this.stop) {
if(start > this.stop) {
newTracks = stop - start + 1;
} else {
long after = stop - this.stop;
if(start >= this.start) {
newTracks = after;
} else {
//both sides (not reached)
newTracks = (start - this.start) + after;
}
}
this.stop = stop;
} else {
//take care of holes
}
return newTracks;
}
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long N = in.nextLong();
long M = in.nextLong();
int K = in.nextInt();

long lamppost = N*M;
//System.out.println(N + ", " + M + ", " + K);
Map<Long, MyRow> map = new HashMap<>();
for(int i = 0; i < K; i++) {
long row = in.nextLong();
long start = in.nextLong();
long stop = in.nextLong();

MyRow theRow = map.get(row);
if(theRow == null) {
theRow = new MyRow();
}
lamppost -= newTracks;
map.put(row, theRow);
}
System.out.println(lamppost);
}
}```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class T {
public:
long r;
long c1;
long c2;
long d;
bool operator<( const T& t ) const {
if (r != t.r) {
return r < t.r;
}

return c1 < t.c1;
}
};

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
long n, m;
int k;

scanf("%ld %ld %d", &n, &m, &k);
vector<T> v(k);
for(int i = 0; i < k; i++) {
T t;
scanf("%ld %ld %ld", &t.r, &t.c1, &t.c2);
t.d = t.c2 - t.c1 + 1;
v[i] = t;
}

sort(v.begin(), v.end());

long non_empty_cells = 0;
int pt = -1;
for(int i = 0; i < k; i++) {
// cout << v[i].r << ": " << v[i].c1 << " " << v[i].c2 << endl;
if (v[pt].r != v[i].r || v[pt].c2 < v[i].c1) {
non_empty_cells += v[i].d;
}
else {
//cout << "merging" << endl;
non_empty_cells -= v[pt].d;
v[i].c1 = v[pt].c1;
v[i].c2 = max(v[pt].c2, v[i].c2);
v[i].d = v[i].c2 - v[i].c1 + 1;
non_empty_cells += v[i].d;
}

pt = i;
}

long long total = n * m - non_empty_cells;
cout << total << endl;
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int min(int a, int b)
{
if (a < b)
return a;
else
return b;
}

int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}

typedef struct bridge_ {
unsigned long int row;
unsigned long int start;
unsigned long int end;
struct bridge_ *next;
} bridge;

bridge *row[1001];

static int ctr = 0;

void insert (bridge **head, unsigned int start, unsigned int end, unsigned int row)
{
bridge *prev = NULL;
bridge *new_node = (bridge *)malloc(sizeof(bridge));

new_node->row = row;
new_node->start = start;
new_node->end = end;

if (!node) {
new_node->next = NULL;
return;
}

if(!node) {
} else {
while (node && start > node->start) {
prev = node;
node = node->next;
}
if (!prev) {
} else {
new_node->next = prev->next;
prev->next = new_node;
}
}
}

unsigned long long int add_ranges(bridge *node)
{
unsigned long long int range = 0;
bridge *prev;
int start, end;

while (node != NULL) {
prev = node;
node = node->next;

end = prev->end;
start = prev->start;

if (node != NULL && end >= node->start) {
start = min(start, node->start);
end = max(end, node->end);
//printf("\n%d %d\n", start, end);
while (node != NULL && end >= node->start) {
end = max(end, node->end);
node = node->next;
}
}
range += end - start + 1;
}
return range;
}

{
printf("\n");
while(tmp != NULL) {
printf("%ld %ld %ld-->", tmp->row, tmp->start, tmp->end);
tmp = tmp->next;
}
printf("NULL\n");
}

int find_entry(int r)
{
int i;
for (i = 0; i < ctr; i++) {
if (!row[i])
continue;
if (row[i]->row == r)
return i;
}
return -1;
}

int main() {
unsigned long long n, m, t;
unsigned long long i, r1, c1, c2;
unsigned long long sum = 0;
unsigned int idx;

scanf("%lld%lld%lld", &n, &m, &t);

sum = n * m;

for (i = 1; i <= t; i++)
row[i] = NULL;

for (i = 1; i <= t; i++) {
scanf("%lld %lld %lld", &r1, &c1, &c2);
idx = find_entry(r1);
if (idx == -1) {
idx = ctr;
ctr++;
}
insert(&row[idx], c1, c2, r1);
}

/* for (i = 0; i < ctr; i++)
print_row(row[i]); */

for (i = 0; i < ctr; i++) {
}

printf("%lld\n", sum);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
```

{"mode":"full","isActive":false}