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) } } }