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.

HackerRank Gridland Metro problem solution


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)

{"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) {
                    //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);
    }
}

{"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 *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 %d\n", 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("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++) {
        sum -= add_ranges(row[i]);
    }

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

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