Looking at a figure one is lead to the following algorithm which traces out the graph of $f$:
One may assume $a_1< a_2 < \ldots < a_n$. If $0 < a_1$ or $a_n < 0$ then $m:=\min_x f(x)=-\infty$. Otherwise for $x$ large negative one has $f(x)=a_1 x + b_1$ and for $x$ large positive one has $f(x)=a_n x+b_n$. Therefore put $x_1:=-\infty$, $j_1:=1$ and for $k\geq1$ define recursively $$ r_i := {b_{j_k}-b_i\over a_i-a_{j_k}} \ (j_k < i \leq n),\quad x_{k+1}:=\min_{j_k < i \leq n}\ r_i\ ,\quad j_{k+1}:=\arg\min_{j_k < i \leq n} r_i\ .$$ When for the first time $a_{j_{k+1}}\geq0$ the minimum is found: One has $m=a_{j_k}x_{k+1}+b_{j_k}$.
As a bonus I propose the following algorithm which seems more sophisticated and is maybe faster:
Put $g_i(x):=a_i x+ b_i$ and denote by $g_i\wedge g_j$ the point of intersection of the two graphs. Assume for simplicity $ a_1 < \ldots a_s<0 < a_{s+1} < \ldots < a_n$. Then apply in succession
- Put $l:=1$, $\ r:=n$.
- Put $(\xi,\eta):= g_l\wedge g_r\ $.
- If $l=s$ and $r=s+1$, goto 7.
- Let $\tau:=\max_{l < i < r}\ g_i(\xi)\ ,\quad p:=\arg\max_{l < i < r}\ g_i(\xi).$
- If $\tau\leq \eta$ goto 7.
- If $p\leq s$ put $l:=p$, else put $r:=p$; then goto 2.
- $m=\eta$.
