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