Real estate agents | 2 Dimensional & Algorithms Practice Problems

All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Real estate agents

Tag(s):

2D dynamic programming, Algorithms, Binary Search, Dynamic Programming

Problem

Editorial

Analytics

There are $m$ real estate agents in the city. There is a street containing $n$ houses in a straight line and they are numbered from $1$ to $n$. The $ i^{th} $ agent sells the houses with numbers from $I_i$ to $r_i$ and gets $c_i$ dollars as the commission fee.

Note: The $i^{th}$ agent is paid either $0$ or $c_i$ dollars.

If you want to buy a house, then you are required to pay the commission to all the agents selling that house but each agent can be paid at most once.

If you want to buy exactly $k$ houses in the city, then determine the minimum amount of money that you must pay in dollars.

Input format

First line: Three space-separated integers $n, m,$ and $k$ denoting the number of houses, the number of agents, and the number of houses you want to buy
Next $n$ lines: Three space-separated integers $l_i, r_i,$ and $c_i$ denoting the range of houses and the commission earned by the $i^{th}$ agent

Output format

In a single line, print one number that represents the minimum amount of money that you are required to pay to buy exactly $k$ houses.

Constraints

$1 \leq n \leq 2000\\ 1 \leq m \leq 10^{5}\\ 1 \leq k \leq n\\ 1 \leq l_i \leq r_i \leq n\\ 1 \leq c_i \leq 10^{9}$

SAMPLE INPUT

SAMPLE OUTPUT

Explanation

We can buy houses with numbers $$[5,6,9,10]$$. In this situation we have to pay only 5$. (paying the second agent)

Time Limit: 2,0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme: Marks are awarded when all the testcases pass.

Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

View all comments

Contributor

This Problem was Asked in

Challenge Name

March Easy '20

All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

2D dynamic programming, Algorithms, Binary Search, Dynamic Programming

CODE EDITOR

Contributor

This Problem was Asked in

Поделиться в социальных сетях