HackerRank: gridland-metro

The city of Gridland is represented as an matrix where the rows are numbered from to and the columns are numbered from to .

Gridland has a network of train tracks that always run in straight horizontal lines along a row. In other words, the start and end points of a train track are and , where represents the row number, represents the starting column, and represents the ending column of the train track.

The mayor of Gridland is surveying the city to determine the number of locations where lampposts can be placed. A lamppost can be placed in any cell that is not occupied by a train track.

Given a map of Gridland and its train tracks, find and print the number of cells where the mayor can place lampposts.

Note: A train track may (or may not) overlap other train tracks within the same row.

Input Format

The first line contains three space-separated integers describing the respective values of (the number of rows), (the number of columns), and (the number of train tracks).
Each line of the subsequent lines contains three space-separated integers describing the respective values of , , and that define a train track.

Output Format
Print a single integer denoting the number of cells where the mayor can install lampposts.

Sample Input
4 4 3
2 2 3
3 1 4
4 4 4

Sample Output
9

This problem can get trickier when the input ranges(train track) information are Long integers.We also need to handle overlapping routes

Gist of the logic :
1.  Store the train track information in a hashmap. I have used row number as the key and LIST of train track info as the value
eg: 2->(5,6)(2,3)
Sort the routes. After sorting above entry would be as below
2->(2,3)(5,6)

2.  Once the entries are sorted, if there is overlapping we need merge the entries.
Few of the important cases that we need to handle:
   a) Input Track information
   1 20
   15 30
   Both of these routes should be merged into 1 30

   b) Input Track information
   5 20
   1 25
   Both of these routes should be merged into 1 25

import scala.collection.immutable.List

object Solution {
  
  var routes:scala.collection.mutable.HashSet[String] = new scala.collection.mutable.HashSet[String]()
      
  var new_routes:scala.collection.mutable.HashMap[Long,List[(Long,Long)]] = new scala.collection.mutable.HashMap[Long,List[(Long,Long)]]()
  def main(args: Array[String]): Unit = {
    
    var occupiedGridCount=0L
    val sc = new java.util.Scanner (System.in);
    var row_col_numLines = sc.nextLine()
    var row = row_col_numLines.split(" ")(0).toLong
    var col = row_col_numLines.split(" ")(1).toLong
    var numLines = row_col_numLines.split(" ")(2).toInt
    var entries:Array[String] = new Array[String](numLines+1)
    
    for(i<- 1 to numLines)
    {
      entries(i) = sc.nextLine()
    }
    
    
    for(i<- 1 to numLines)
    {
      var row:Long = entries(i).split(" ")(0).toLong
      var start:Long = entries(i).split(" ")(1).toLong
      var end:Long = entries(i).split(" ")(2).toLong
      FillMatrix(row,start,end)
    }
   
    //Sort the entries
    for((row,list) <- new_routes)
    {
      var sorted_list = list.sortBy(r=>(r._1,r._2))   
      new_routes += (row->sorted_list)
    }
    
    
    for((row,list) <- new_routes)
    {
      occupiedGridCount =  occupiedGridCount + getOccupiedGrdCount(list)
    }
    println(row*col-occupiedGridCount)
  }
  
  def getOccupiedGrdCount(list:List[(Long,Long)]):Long=
  {
      //This code takes care of merging the overlapping routes and returns the sum of length of all the routes
      var cur_c1 = 0L
      var cur_c2 = 0L
      var concatList:List[(Long,Long)] = List[(Long,Long)]()
      
      //If there are more than one entry associated with a row
      if(list.size >= 1)
      {
        
        //concatList.::
         for((c1,c2)<- list)
         {
           //When cur_c1, cur_c2 are 0 it means we are processing the first entry
           if(cur_c1 == 0 && cur_c2 == 0)
           {
               cur_c1 = c1
               cur_c2 = c2
           }
           else
           {
             //Eg: 2->(2,5)(3,10) , in this case (3,10) are (c1,c2) 
             if(c1 <= cur_c2 && c2 >=cur_c2)
             {
               cur_c2 = c2
             }
             //Eg: 2->(2,100)(3,6) , in this case (3,6) are (c1,c2)
             else if(c1 <= cur_c2 && c2 < cur_c2)
             {
               //ignore the entry since it cur_c1 and cur_c2 encompasses c1 and c2
               
             }
             //No Overlapping : Eg: 2->(2,5)(8,10) , in this case (8,10) are (c1,c2)
             else
             {
               //Put the entries to the list since there is no more overlapping
               concatList=concatList.::(cur_c1,cur_c2)
               cur_c1 = c1
               cur_c2 = c2
             }
           }
             
         }
         concatList=concatList.::(cur_c1,cur_c2)
       }
      //If there is only one entry associated with the row
      else
      {
       concatList=concatList++list 
      }

      //Caculate the sum (please note +1 )
      var gridCount = 0L
      for((c1,c2)<-concatList)
        gridCount+=(c2-c1)+1
      return gridCount
    }
    
  

  def FillMatrix(rownum:Long,start:Long,end:Long)
  {
    var entry = new_routes.get(rownum)
    //If first entry for the row
    if(new_routes.contains(rownum) == false)
    {
      new_routes += (rownum->List((start,end)))
    }
    //If entry already exists,the append the entry to existing list
    else
    {
      var cur_list = new_routes.get(rownum).get
      cur_list = cur_list.:: (start,end)
      new_routes += (rownum->cur_list)
    }
  }


}

 

Leave a Reply

Your email address will not be published. Required fields are marked *