# Mirko at the Construction Site – HackerRank Solution

In this post, we will solve Mirko at the Construction Site HackerRank Solution. This problem (Mirko at the Construction Site) is a part of HackerRank Functional Programming series.

Contents

Mirko is monitoring a construction site. He monitors N buildings enumerated from 1 to N, starting from the left. For each building, he knows the current number of floors and the number of floors built on each day. He needs to know the answer to Q queries. The answer to each query is the index of the tallest building after T days, as defined by the query. Your task is to help Mirko find the answers to these queries.

## Input Format

The first line consists of the numbers N and Q. The second line consists of N integers, where the ith integer represents the initial height of the ith building. The third line consists of N integers, where the ith integer represents the number of floors erected in one day for the ith building. The following Q lines consist of the integer, T, representing the day in the query.

## Output Format

For each query, output one number which represents the index of the tallest building after T days. If there is more than one building, output the building with the greatest index in the input array (with indexes starting at 1).

## Constraints

• 1 <= N <= 105
• 1 <= Q <= 105
• Every other integer in the input will fit in a 32-bit signed integer. And they will be non-negative integers.

Sample Input

``````3 6
7 5 1
1 2 3
0
1
2
3
4
5``````

Sample Output

``````1
1
2
2
3
3  ``````

Explanation

Query #1: The height at the end of the 0th day will be {7, 5, 1}. Here, the 1st building is the tallest.
Query #2: The height at the end of the 1st day will be {8, 7, 4}. Here, the 1st building is the tallest.
Query #3: The height at the end of 2nd day will be {9, 9, 7}. Here, the 1st and 2nd buildings are the tallest, while the 2nd is the larger index.
Query #4: The height at the end of 3rd day will be {10, 11, 10}. Here, the 2nd building is the tallest.
Query #5: The height at the end of 4th day will be {11, 13, 13}. Here, the 2nd and 3rd buildings are the tallest, while the 3rd is the larger index.
Query #6: The height at the end of 5th day will be {12, 15, 16}. Here, the 3rd building is the tallest.

## Solution – Mirko at the Construction Site – HackerRank Solution

Scala

```import java.util.Scanner

object Solution {
def main(args: Array[String]): Unit = {
val sc = new Scanner(System.in)

sc.nextInt
val q = sc.nextInt
sc.nextLine
val initials = sc.nextLine.split(" ").map(_.toInt)
val steps = sc.nextLine.split(" ").map(_.toInt)

case class Query(index: Int, time: Int)
val queries = (0 until q).map(Query(_, sc.nextInt)).sortBy(_.time)

sc.close()

case class Building(index: Int, initial: Long, step: Long) extends Ordered[Building] {
override def compare(that: Building): Int = {
if (this.step < that.step) -1
else if (this.step > that.step) 1
else if (this.initial < that.initial) -1
else if (this.initial > that.initial) 1
else this.index.compareTo(that.index)
}

def height(time: Long): Long = initial + step * time
}

val buildings: List[Building] = initials.indices.map(i => Building(i + 1, initials(i), steps(i)))
.groupBy(_.step)
.map { case (_, list) => list.maxBy(_.initial) }
.toList
.sorted

def intersection(b0: Building, b1: Building) = (b1.initial.toDouble - b0.initial) / (b0.step.toDouble - b1.step)

@scala.annotation.tailrec
def prepare(buildings: List[Building], acc: List[Building]): List[Building] = buildings match {
case Nil => acc
case v :: Nil => v :: acc
case v0 :: v1 :: vs =>
val inter0 = intersection(highest, v0)
val inter1 = intersection(highest, v1)

if (inter0 < inter1 || inter0 == inter1 && v0.index > v1.index)
prepare(v1 :: vs, v0 :: acc)
else if (acc.tail.isEmpty)
prepare(v1 :: vs, acc)
else
prepare(acc.head :: v1 :: vs, acc.tail)
}

case class Pair(queryIndex: Int, highestIndex: Int)
case class Acc(buildings: List[Building], highestIndices: List[Pair])
val answer = queries.foldLeft(Acc(highBuildings, Nil))((acc, q) => {
@scala.annotation.tailrec
def findHighest(buildings: List[Building]): Acc = buildings match {
case b :: Nil => Acc(acc.buildings, Pair(q.index, b.index) :: acc.highestIndices)
case b0 :: b1 :: bs =>
val inter = intersection(b0, b1)
if (inter > q.time || inter == q.time && b0.index > b1.index)
Acc(buildings, Pair(q.index, b0.index) :: acc.highestIndices)
else
findHighest(b1 :: bs)
case Nil => throw new Exception("Impossible")
}

findHighest(acc.buildings)
})