Ubuntu – Build-essential not installing because of unmet dependencies in Ubuntu 18.10

build-essential installation is failing on freshly installed Ubuntu 18.10 with this error:

$ sudo apt install build-essential
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 build-essential : Depends: libc6-dev but it is not going to be installed or
                            libc-dev
                   Depends: gcc (>= 4:7.3) but it is not going to be installed
                   Depends: g++ (>= 4:7.3) but it is not going to be installed
                   Depends: dpkg-dev (>= 1.17.11) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

Installation via deb file is also failing.

I think this package is not correctly ported to 18.10 because its asking for outdated dependencies (dependencies versions available in 18.04 LTS). What is the safest way to install it?

Note that I have already installed it (on some other machine) with unsafe methods e.g. downgrading packages via aptitude but this method breaks too many other packages.

Update #1:

libc6-dev installation is failing.

$ sudo apt install libc6-dev
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 libc6-dev : Depends: libc6 (= 2.27-3ubuntu1) but 2.28-0ubuntu1 is to be installed
             Depends: libc-dev-bin (= 2.27-3ubuntu1)
E: Unable to correct problems, you have held broken packages.

I don't know why apt is looking for older versions of libc6 and libc-dev-bin.

Similarly, apt shows that gcc also depends on previous version of cpp.

$ sudo apt install gcc
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 gcc : Depends: cpp (= 4:8.1.0-2ubuntu1) but 4:8.2.0-1ubuntu1 is to be installed
       Depends: gcc-8 (>= 8.1.0-4~) but it is not going to be installed
       Recommends: libc6-dev but it is not going to be installed or
                   libc-dev
E: Unable to correct problems, you have held broken packages.

Update #2: apt-cache policy output

$ apt-cache policy gcc cpp
gcc:
  Installed: (none)
  Candidate: 4:8.1.0-2ubuntu1
  Version table:
     4:8.1.0-2ubuntu1 500
        500 http://pk.archive.ubuntu.com/ubuntu cosmic/main amd64 Packages
cpp:
  Installed: 4:8.2.0-1ubuntu1
  Candidate: 4:8.2.0-1ubuntu1
  Version table:
 *** 4:8.2.0-1ubuntu1 100
        100 /var/lib/dpkg/status
     4:8.1.0-2ubuntu1 500
        500 http://pk.archive.ubuntu.com/ubuntu cosmic/main amd64 Packages