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:
trackadded = False
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]))
trackadded = True
break
if not trackadded:
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)
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) {
//add hole
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) {
//add hole
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();
}
long newTracks = theRow.add(start, stop);
lamppost -= newTracks;
map.put(row, theRow);
}
System.out.println(lamppost);
}
}
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;
}
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 *node = *head;
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;
*head = new_node;
return;
}
node = *head;
if(!node) {
*head = new_node;
} else {
while (node && start > node->start) {
prev = node;
node = node->next;
}
if (!prev) {
new_node->next = *head;
*head = new_node;
} 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 %dn", start, end);
while (node != NULL && end >= node->start) {
end = max(end, node->end);
node = node->next;
}
}
range += end - start + 1;
}
return range;
}
void print_row(bridge *head)
{
bridge *tmp = head;
printf("n");
while(tmp != NULL) {
printf("%ld %ld %ld-->", tmp->row, tmp->start, tmp->end);
tmp = tmp->next;
}
printf("NULLn");
}
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++) {
sum -= add_ranges(row[i]);
}
printf("%lldn", sum);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}