To install OpenJDK 11 in Ubuntu, use the commands listed below.

1. Add the repository

sudo add-apt-repository ppa:openjdk-r/ppa

2. Update package list

sudo apt-get update

3. Install openjdk-11-jdk

sudo apt install openjdk-11-jdk

Now it is possible to install openjdk-11 this way:

sudo apt-get install openjdk-11-jdk

(Previously it installed openjdk-10, but not anymore)

For Ubuntu 22.04, you should be able to simply:
sudo apt install openjdk-21-jdk

It's in the Universe repository, so be sure you have that enabled.

It wasn't available yet when you asked the question, but it is now.

If you add a PPA or other non-Ubuntu version of OpenJDK, remember that it's likely to be incompatible with the (supported Ubuntu repository) Ubuntu package. So keep track of what you install; you might need to remove all of it.

You likely don't have the i386 architecture enabled. Do the following:

sudo dpkg --add-architecture i386
sudo apt update
sudo apt install openjdk-11-jdk:i386

apt can’t locate openjdk-16-jre-headless because the OpenJDK 16 packages aren’t available in any Debian release.

The only release available to you in Debian 10 is OpenJDK 11. Debian 11 has OpenJDK 17. Both of these are releases with long-term support.

You made a typo: the error message says that it can't find openjdk-8-headless.

But the correct package name is openjdk-8-jre-headless. It is available and installs without any issues on 20.04.

UPDATE: installation without root privileges below

I advise you to not install packages manually on ubuntu system if there is already a (semi-official) repository able to solve your problem. Further, use Oracle JDK for development, just to avoid (very sporadic) compatibility issues (i've tried many years ago, it's surely better now).

Add the webupd8 repo to your system:

Copysudo add-apt-repository ppa:webupd8team/java
sudo apt-get update

Install your preferred version of jdk (versions from java-6 to java-9 available):

Copysudo apt-get install oracle-java8-installer

You can also install multiple version of jdk, mixing openjdk and oracle versions. Then you can use the command update-java-alternatives to switch between installed version:

Copy# list available jdk
update-java-alternatives --list

# use jdk7
sudo update-java-alternatives --set java-7-oracle

# use jdk8
sudo update-java-alternatives --set java-8-oracle

Requirements

If you get add-apt-repository: command not found be sure to have software-properties-common installed:

Copysudo apt-get install software-properties-common

If you're using an older version Ubuntu:

Copysudo apt-get install python-software-properties

JDK installation without root privileges

If you haven't administrator rights on your target machine your simplest bet is to use sdkman to install the zulu certified openjdk:

Copycurl -s "https://get.sdkman.io" | bash
source "$HOME/.sdkman/bin/sdkman-init.sh"
sdk install java

NOTE: sdkman allow to install also the official Oracle JDK, although it's not a the default option. View available versions with:

Copysdk ls java

Install the chosen version with:

Copysdk install java <version>

For example:

Copysdk install java 9.0.1-oracle

Glossary of commands

• sudo <command> [command_arguments]: execute a command with the superuser privilege.

• add-apt-repository <PPA_id>: Ubuntu (just like every Debian derivatives and generally speaking every Linux distribution) has a main repository of packages that handle things like package dependencies and updating. In Ubuntu is possible to extend the main repository using a PPA (Personal Package Archive) that usually contains packages not available in the system (just like oracle jdk) or updated versions of available ones (example: LibreOffice 5 in LTS is available only through this PPA).

• apt-get [install|update|upgrade|purge|...]: it's "the" command-line package handler used to manipulate the state of every repository on the system (installing / updating / upgrading can be viewed as an alteration of the repository current state).

In our case: with the command sudo add-apt-repository ppa:webupd8team/java we inform the system that the next repository update must retrieve packages information also from webupd8 repo.

With sudo apt-get update we actually update the system repository (all this operations requires superuser privileges, so we prepend sudo to the commands).

sudo apt-get install oracle-java8-installer

• update-java-alternatives (a specific java version of update-alternatives): in Ubuntu several packages provides the same functionality (browse the internet, compile mails, edit a text file or provides java/javac executables...). To allows the system to choose the user favourites tool given a specific task a mechanism using symlinks under /etc/alternatives/ is used. Try to update the jdk as indicated above (switch between java 7 and java 8) and view how change the output of this command:

  ls -l /etc/alternatives/java*

In our case: sudo update-java-alternatives --set java-8-oracle update symlinks under /etc/alternatives to point to java-8-oracle executables.

Extras:

• man <command>: start using man to read a really well written and detailed help on (almost) every shell command and its options (every command i mention in this little answer has a man page, try man update-java-alternatives).

• apt-cache search <search_key>: query the APT cache to search for a package related with the search_key provided (can be the package name or some word in package description).

• apt-cache show <package>: provides APT information for a specific package (package version, installed or not, description).

Running

Copysudo apt update

before trying to install a second JDK (g00se suggested I had to) helped. It was ChatGPT's advice. If you need to know where the JDK is installed, try (also GPT's idea)

Copyupdate-alternatives --list java

With that information, you should be able to register that JAVA_HOME thing. In my case, it was

Copyexport JAVA_HOME=/usr/lib/jvm/java-17-openjdk-amd64

I hope it helps somebody one day